Introduction to Planning Problems in AI

Author

Your Name

Published

February 5, 2025

Introduction

This document provides a comprehensive overview of planning problems in Artificial Intelligence (AI), with a particular emphasis on modeling these problems using Answer Set Programming (ASP). We will delve into several classic examples, including the Wolf, Goat, and Cabbage problem, the Wine Barrel problem, the Towers of Hanoi, and the 15-Puzzle. These examples will serve to illustrate fundamental concepts such as:

Time Representation: How to model the temporal aspect of planning problems.
Action Preconditions and Effects: Defining the conditions necessary for an action to occur and its consequences.
Inertia Rules: Specifying what remains unchanged when an action is performed.
Complexity: Understanding the distinction between NP-complete and PSPACE-complete problems in the context of planning.

The primary objectives of this document are to:

Understand the process of modeling planning problems.
Learn how to represent time and actions within a formal framework.
Recognize the inherent complexity of planning problems and their implications.

By the end of this document, readers should have a solid foundation in the core principles of planning in AI and be able to apply these principles to model and solve various planning challenges.

The Wolf, Goat, and Cabbage Problem

Problem Description

The classic Wolf, Goat, and Cabbage problem involves a man who needs to transport a wolf, a goat, and a cabbage across a river. He has a small boat that can only carry himself and one other item at a time. The constraints are that the wolf cannot be left alone with the goat, and the goat cannot be left alone with the cabbage. The objective is to find a sequence of actions (a plan) that safely transports all items to the other side of the river. This problem is a fundamental example of a planning problem that requires reasoning about state transitions and constraints.

Modeling the Problem

To model this problem, we use a discrete notion of time and define the following:

Time: $t \in \{0, 1, ..., n\}$, where $n$ represents the unknown number of time steps required to solve the problem.
Places: The possible locations are the left bank, the right bank, and the boat.
Objects: The items to be transported are the man, the wolf, the goat, and the cabbage.

Definition 1 (State). A state at any time $t$ is defined by the location $p$ of each object $o$. We represent this with the predicate $on(t, o, p)$, indicating that object $o$ is at place $p$ at time $t$.

Initial State

At the initial time $t=0$, all objects are on the left bank of the river:

$on(0, \text{Man}, \text{Left})$
$on(0, \text{Wolf}, \text{Left})$
$on(0, \text{Goat}, \text{Left})$
$on(0, \text{Cabbage}, \text{Left})$

Constraints

The problem constraints are:

The wolf and goat cannot be left alone together: \[\label{eq:wgc_constraint_1} \forall t, p: on(t, \text{Goat}, p) \land on(t, \text{Cabbage}, p) \rightarrow on(t, \text{Man}, p)\] This constraint ensures that if both the goat and the cabbage are in the same place at time $t$, the man must also be present.
The goat and cabbage cannot be left alone together: \[\label{eq:wgc_constraint_2} \forall t, p: on(t, \text{Wolf}, p) \land on(t, \text{Goat}, p) \rightarrow on(t, \text{Man}, p)\] This constraint ensures that if both the wolf and the goat are in the same place at time $t$, the man must also be present.
The boat can carry at most two objects (including the man): \[\label{eq:wgc_constraint_3} \forall t: 0 \leq \sum_{o} on(t, o, \text{Boat}) \leq 2\] This constraint limits the capacity of the boat to a maximum of two objects at any given time $t$.

Action Effects

The effects of moving an object using the boat are modeled as follows:

If an object is on the left bank at time $t$ and on the boat at time $t+1$, it will be on the right bank at time $t+2$: \[\label{eq:wgc_action_effect_1} \forall t, o: on(t, o, \text{Left}) \land on(t+1, o, \text{Boat}) \rightarrow on(t+2, o, \text{Right})\] This rule describes the transition of an object from the left bank to the right bank after being on the boat.
Similarly, if an object is on the right bank at time $t$ and on the boat at time $t+1$, it will be on the left bank at time $t+2$: \[\label{eq:wgc_action_effect_2} \forall t, o: on(t, o, \text{Right}) \land on(t+1, o, \text{Boat}) \rightarrow on(t+2, o, \text{Left})\] This rule describes the transition of an object from the right bank to the left bank after being on the boat.
If an object is on the boat at time $t$, the man must also be on the boat: \[\label{eq:wgc_action_effect_3} \forall t, o: on(t, o, \text{Boat}) \rightarrow on(t, \text{Man}, \text{Boat})\] This rule ensures that the man is always present in the boat when any other object is being transported.

Inertia Rules

Inertia rules specify that objects not involved in an action remain in their previous state. In this case, it is sufficient to state that objects cannot jump directly from the left bank to the right bank or vice versa: \[\begin{aligned} \label{eq:wgc_inertia_1} \forall t, o: \neg (on(t, o, \text{Left}) \land on(t+1, o, \text{Right})) \\ \label{eq:wgc_inertia_2} \forall t, o: \neg (on(t, o, \text{Right}) \land on(t+1, o, \text{Left}))\end{aligned}\] These rules prevent objects from changing their location without using the boat.

Goal State

The goal is to have all objects on the right bank at time $n$: \[\label{eq:wgc_goal_state} \text{Final} \leftarrow on(n, \text{Man}, \text{Right}) \land on(n, \text{Wolf}, \text{Right}) \land on(n, \text{Goat}, \text{Right}) \land on(n, \text{Cabbage}, \text{Right})\] To ensure that the solver reaches the goal, we add a constraint that states that it is impossible not to reach the final state: \[\label{eq:wgc_goal_enforce} \neg \text{Final} \rightarrow \text{False}\]

ASP Code

The following ASP code encodes the Wolf, Goat, and Cabbage problem:

% Define time, places, and objects
time(0..n).
place(left). place(right). place(boat).
object(man). object(wolf). object(goat). object(cabbage).

% Initial state
on(0, man, left). on(0, wolf, left). on(0, goat, left). on(0, cabbage, left).

% Constraints
on(T, man, P) :- time(T), place(P), on(T, goat, P), on(T, cabbage, P).
on(T, man, P) :- time(T), place(P), on(T, wolf, P), on(T, goat, P).
0 { on(T, O, boat) : object(O) } 2 :- time(T).

% Action effects
on(T+2, O, right) :- on(T, O, left), on(T+1, O, boat), time(T), time(T+2).
on(T+2, O, left) :- on(T, O, right), on(T+1, O, boat), time(T), time(T+2).
on(T, man, boat) :- on(T, O, boat), object(O), time(T).

% Inertia rules
:- on(T, O, left), on(T+1, O, right), time(T), time(T+1), object(O).
:- on(T, O, right), on(T+1, O, left), time(T), time(T+1), object(O).

% Goal state
final :- on(n, man, right), on(n, wolf, right), on(n, goat, right), on(n, cabbage, right).
:- not final.

% Define the action of moving onto the boat
moved(T, O, From, To) :- on(T, O, From), on(T+1, O, To), From != To.

% Ensure there is always an action
:- not moved(T, O, From, To), time(T), T < n.

% Show the moves
#show moved/4.

Solving the Problem

The problem is solved by iteratively calling an ASP solver with increasing values of $n$ until a solution is found. The minimum $n$ for which a solution is found represents the shortest plan to move all objects to the right bank. This iterative approach is necessary because the length of the plan is not known in advance. The solver explores the space of possible actions and states, guided by the constraints and rules defined in the ASP code.

The Wine Barrel Problem

Problem Description

The Wine Barrel problem involves three barrels with capacities of 12, 7, and 5 liters. Initially, the 12-liter barrel is full of wine, while the 7-liter and 5-liter barrels are empty. The objective is to reach a state where the 12-liter and 7-liter barrels each contain exactly 6 liters of wine, and the 5-liter barrel is empty. The only allowed action is to pour wine from one barrel to another until either the source barrel is empty or the destination barrel is full. This problem highlights the challenge of achieving a specific distribution of resources through a sequence of constrained actions.

Modeling the Problem

To model this problem, we define the following:

Time: $t \in \{0, 1, ..., n\}$, where $n$ is the unknown number of steps.
Barrels: $b \in \{5, 7, 12\}$, representing the three barrels with their respective capacities.
Amount: $a \in \{0, 1, ..., 12\}$, representing the possible integer amounts of wine in liters that a barrel can contain.

Definition 2 (State). A state at any time $t$ is defined by the amount $a$ of wine in each barrel $b$. We represent this with the predicate $contains(t, b, a)$, indicating that barrel $b$ contains $a$ liters of wine at time $t$.

Actions

At each time step $t$, we can pour wine from barrel $x$ to barrel $y$, where $x \neq y$. This action is represented by the predicate $pour(t, x, y)$. There are six possible actions:

$pour(t, 12, 7)$
$pour(t, 12, 5)$
$pour(t, 7, 12)$
$pour(t, 7, 5)$
$pour(t, 5, 12)$
$pour(t, 5, 7)$

We enforce that exactly one action occurs at each time step: \[\label{eq:wb_action_constraint} \forall t: \sum_{x, y, x \neq y} pour(t, x, y) = 1\]

Initial State

The initial state at time $t=0$ is:

$contains(0, 12, 12)$
$contains(0, 7, 0)$
$contains(0, 5, 0)$

Goal State

The goal state is defined as:

$contains(n, 12, 6)$
$contains(n, 7, 6)$
$contains(n, 5, 0)$

We enforce the goal state by defining the predicate final and ensuring that it is reached: \[\begin{aligned} \label{eq:wb_goal_state_def} \text{Final} &\leftarrow contains(n, 12, 6) \land contains(n, 7, 6) \land contains(n, 5, 0) \\ \label{eq:wb_goal_state_enforce} \neg \text{Final} &\rightarrow \text{False}\end{aligned}\]

Action Preconditions and Effects

Precondition: We cannot pour from an empty barrel or into a full barrel.
Effect: If we pour from barrel $x$ to barrel $y$ at time $t$, there are two cases:
1. If the amount in $x$ ($LX$) is less than or equal to the remaining capacity in $y$ ($Y - LY$), then $x$ becomes empty, and $y$ contains the sum of the amounts ($LX + LY$).
2. If the amount in $x$ ($LX$) is greater than the remaining capacity in $y$ ($Y - LY$), then $y$ becomes full, and $x$ contains the remaining amount ($LX - (Y - LY)$).

Inertia Rules

The barrel not involved in the pouring action retains its amount of wine. This is modeled by ensuring that if a barrel $B$ is not the source ($X$) or destination ($Y$) of a pour action, its content remains unchanged between time $T$ and $T+1$.

ASP Code

The following ASP code encodes the Wine Barrel problem:

% Define time, barrels, and amounts
time(0..n).
barrel(5). barrel(7). barrel(12).
amount(0..12).

% Actions
1 { pour(T, X, Y) : barrel(X), barrel(Y), X != Y } 1 :- time(T), T < n.

% Initial state
contains(0, 12, 12).
contains(0, 7, 0).
contains(0, 5, 0).

% Goal state
final :- contains(n, 12, 6), contains(n, 7, 6), contains(n, 5, 0).
:- not final.

% Action preconditions
:- pour(T, X, Y), contains(T, X, 0).
:- pour(T, X, Y), contains(T, Y, Y).

% Action effects
contains(T+1, X, 0) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY >= LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY).
contains(T+1, Y, LX + LY) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY >= LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY).
contains(T+1, X, LX - (Y - LY)) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY < LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY).
contains(T+1, Y, Y) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY < LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY).

% Inertia rules
contains(T+1, B, A) :- pour(T, X, Y), contains(T, B, A), barrel(B), B != X, B != Y, time(T), time(T+1), amount(A).

% Show the actions
#show pour/3.

The Towers of Hanoi

Problem Description

The Towers of Hanoi is a classic mathematical puzzle involving $N$ disks of different sizes and three pegs. Initially, all disks are stacked on one peg in decreasing order of size, forming a tower. The objective is to move the entire tower to another peg, adhering to the following rules:

Only one disk can be moved at a time.
A disk can only be moved if it is the topmost disk on a peg.
A larger disk cannot be placed on top of a smaller disk.

This problem is often used to illustrate recursion and algorithmic problem-solving.

Modeling the Problem

To model the Towers of Hanoi problem, we define:

Time: $t \in \{0, 1, ..., n\}$, where $n$ is the unknown number of steps.
Pegs: $p \in \{1, 2, 3\}$, representing the three pegs.
Disks: $d \in \{1, 2, ..., N\}$, representing the $N$ disks, where 1 is the smallest and $N$ is the largest.

Definition 3 (State). A state at any time $t$ is defined by the position of each disk $d$ on a peg $p$. We represent this with the predicate $in(t, d, p)$, indicating that disk $d$ is on peg $p$ at time $t$. Additionally, we define a predicate $on(t, d_1, d_2)$ to indicate that disk $d_1$ is directly on top of disk $d_2$ at time $t$.

Actions

At each time step $t$, we can move the top disk from peg $x$ to peg $y$, where $x \neq y$. This action is represented by the predicate $move(t, x, y)$. There are six possible actions:

$move(t, 1, 2)$
$move(t, 1, 3)$
$move(t, 2, 1)$
$move(t, 2, 3)$
$move(t, 3, 1)$
$move(t, 3, 2)$

We enforce that exactly one action occurs at each time step: \[\label{eq:toh_action_constraint} \forall t: \sum_{x, y, x \neq y} move(t, x, y) = 1\]

Initial State

Initially, all disks are on peg 1, stacked in decreasing order of size:

$in(0, d, 1)$ for all $d \in \{1, 2, ..., N\}$
$on(0, d, d+1)$ for all $d \in \{1, 2, ..., N-1\}$
$on(0, N, \text{floor})$, where floor represents the base of the peg.

Goal State

The goal state is to have all disks on peg 2, stacked in decreasing order of size:

$in(n, d, 2)$ for all $d \in \{1, 2, ..., N\}$
$on(n, d, d+1)$ for all $d \in \{1, 2, ..., N-1\}$
$on(n, N, \text{floor})$

The goal is reached when all disks are on peg 2 in the correct order.

Action Preconditions and Effects

Precondition: We cannot move from an empty peg or place a larger disk on a smaller one.
Effect: If we move from peg $x$ to peg $y$ at time $t$, the top disk of peg $x$ is moved to the top of peg $y$.

Inertia Rules

Disks not involved in the move action retain their positions. This is ensured by specifying that if a disk has not been moved, its position and the disk it is on top of remain the same.

ASP Code (by Martin Gebser)

The following ASP code, originally developed by Martin Gebser, encodes the Towers of Hanoi problem:

% Define time, pegs, and disks
time(0..n).
peg(1..3).
disk(1..N).

% Actions
1 { move(T, X, Y) : peg(X), peg(Y), X != Y } 1 :- time(T), T < n.

% Initial state
in(0, D, 1) :- disk(D).
on(0, D, D+1) :- disk(D), D < N.
on(0, N, floor).

% Goal state
goal :- in(n, D, 2) : disk(D).
:- not goal.

% Auxiliary predicates
covered(T, D2) :- on(T, D1, D2), disk(D1), disk(D2).
top(T, A, D) :- in(T, D, A), not covered(T, D).
empty(T, A) :- peg(A), not in(T, D, A) : disk(D).
top(T, A, floor) :- empty(T, A).
moved_disk(T, D) :- move(T, A, B), top(T, A, D).

% Action preconditions
:- move(T, A, B), empty(T, A).
:- on(T, D1, D2), D1 >= D2.

% Action effects
on(T+1, D1, D2) :- move(T, A, B), top(T, A, D1), top(T, B, D2).
in(T+1, D, B) :- move(T, A, B), top(T, A, D).

% Inertia rules
on(T+1, D1, D2) :- on(T, D1, D2), not moved_disk(T, D1).
in(T+1, D, A) :- in(T, D, A), not moved_disk(T, D).

% Show the moves
#show move/3.

The 15-Puzzle

Problem Description

The 15-Puzzle is a sliding puzzle consisting of a 4x4 grid with 15 numbered tiles and one empty space. The tiles are initially arranged in a scrambled order, and the goal is to arrange them in numerical order by sliding tiles into the empty space. This puzzle is a classic example of a problem that can be solved using planning techniques, requiring a sequence of moves to reach the desired configuration.

Modeling the Problem

To model the 15-Puzzle, we define the following:

Time: $t \in \{0, 1, ..., n\}$, where $n$ is the unknown number of steps.
Rows: $r \in \{0, 1, 2, 3\}$, representing the rows of the grid.
Columns: $c \in \{0, 1, 2, 3\}$, representing the columns of the grid.
Values: $v \in \{0, 1, ..., 15\}$, representing the values of the tiles, where 0 represents the empty space.

Definition 4 (State). A state at any time $t$ is defined by the value $v$ at each position $(r, c)$. We represent this with the predicate $cell(t, r, c, v)$, indicating that the cell at row $r$ and column $c$ contains value $v$ at time $t$.

Actions

At each time step $t$, we can move the empty space (represented by the value 0) up, down, left, or right. This is equivalent to sliding a tile into the empty space. We represent this with the predicate $move(t, d)$, where $d \in \{\text{up}, \text{down}, \text{left}, \text{right}\}$. We enforce that exactly one action occurs at each time step: \[\label{eq:15p_action_constraint} \forall t: \sum_{d} move(t, d) = 1\]

Initial State

The initial state is given by the specific arrangement of tiles. For example, a possible initial state is:

$cell(0, 0, 0, 1)$
$cell(0, 0, 1, 2)$
$cell(0, 0, 2, 3)$
$cell(0, 0, 3, 4)$
$cell(0, 1, 0, 5)$
$cell(0, 1, 1, 6)$
$cell(0, 1, 2, 7)$
$cell(0, 1, 3, 8)$
$cell(0, 2, 0, 9)$
$cell(0, 2, 1, 10)$
$cell(0, 2, 2, 11)$
$cell(0, 2, 3, 12)$
$cell(0, 3, 0, 13)$
$cell(0, 3, 1, 14)$
$cell(0, 3, 2, 15)$
$cell(0, 3, 3, 0)$

Goal State

The goal state is to have the tiles arranged in numerical order, with the empty space in the bottom-right corner: \[\begin{aligned} \label{eq:15p_goal_state_def_1} \text{Final} &\leftarrow cell(n, r, c, 4r + c + 1) \text{ for } r, c \in \{0, 1, 2, 3\}, (r, c) \neq (3, 3) \\ \label{eq:15p_goal_state_def_2} \text{Final} &\leftarrow cell(n, 3, 3, 0)\end{aligned}\] We enforce the goal state by adding the constraint: \[\label{eq:15p_goal_state_enforce} \neg \text{Final} \rightarrow \text{False}\]

Action Preconditions and Effects

Precondition: We cannot move the empty space outside the grid.
Effect: If we move the empty space in direction $d$ at time $t$, the empty space and the adjacent tile in that direction swap positions.

Inertia Rules

Tiles not involved in the move action retain their positions. This is ensured by specifying that if a cell’s value is not changed by a move action, it remains the same in the next time step.

ASP Code

The following ASP code encodes the 15-Puzzle problem:

% Define time, rows, columns, and values
time(0..n).
row(0..3).
col(0..3).
value(0..15).

% Actions
1 { move(T, up); move(T, down); move; move(T, left); move(T, right) } 1 :- time(T), T < n.

% Initial state (example)
cell(0, 0, 0, 1). cell(0, 0, 1, 2). cell(0, 0, 2, 3). cell(0, 0, 3, 4).
cell(0, 1, 0, 5). cell(0, 1, 1, 6). cell(0, 1, 2, 7). cell(0, 1, 3, 8).
cell(0, 2, 0, 9). cell(0, 2, 1, 10). cell(0, 2, 2, 11). cell(0, 2, 3, 12).
cell(0, 3, 0, 13). cell(0, 3, 1, 14). cell(0, 3, 2, 15). cell(0, 3, 3, 0).

% Goal state
final :- cell(n, R, C, R * 4 + C + 1) : row(R), col(C), (R, C) != (3, 3),
         cell(n, 3, 3, 0).
:- not final.

% Action preconditions
:- move(T, up), cell(T, 0, C, 0).
:- move(T, down), cell(T, 3, C, 0).
:- move(T, left), cell(T, R, 0, 0).
:- move(T, right), cell(T, R, 3, 0).

% Action effects
cell(T+1, R-1, C, 0) :- move(T, up), cell(T, R, C, 0), row(R), R > 0.
cell(T+1, R+1, C, 0) :- move(T, down), cell(T, R, C, 0), row(R), R < 3.
cell(T+1, R, C-1, 0) :- move(T, left), cell(T, R, C, 0), col(C), C > 0.
cell(T+1, R, C+1, 0) :- move(T, right), cell(T, R, C, 0), col(C), C < 3.

cell(T+1, R, C, V) :- move(T, up), cell(T, R, C, 0), cell(T, R-1, C, V), V != 0, row(R), R > 0.
cell(T+1, R, C, V) :- move(T, down), cell(T, R, C, 0), cell(T, R+1, C, V), V != 0, row(R), R < 3.
cell(T+1, R, C, V) :- move(T, left), cell(T, R, C, 0), cell(T, R, C-1, V), V != 0, col(C), C > 0.
cell(T+1, R, C, V) :- move(T, right), cell(T, R, C, 0), cell(T, R, C+1, V), V != 0, col(C), C < 3.

% Inertia rules
cell(T+1, R, C, V) :- cell(T, R, C, V), not cell(T+1, R, C, 0), V != 0.

% Show the moves
#show move/2.

Conclusion

In this lecture, we have explored several classic planning problems and their representation using Answer Set Programming (ASP). We have emphasized the importance of:

Modeling time as a discrete sequence of steps.
Defining actions with clear preconditions and effects.
Implementing inertia rules to specify what remains unchanged when an action is performed.
Enforcing the goal state, rather than imposing it as a given fact.

We have also highlighted the distinction between NP-complete and PSPACE-complete problems, noting that many planning problems, due to their inherent complexity, often fall into the latter category.

The key takeaways from this lecture are:

Planning Problems: Involve finding a sequence of actions to reach a desired goal state.
Discrete Time: Time can be discretized and represented as a parameter in predicates, allowing for modeling of temporal sequences.
Action Modeling: Actions have preconditions that must be met for them to be executed and effects that describe the resulting changes in the state.
Inertia Rules: Specify that objects or properties not directly affected by an action remain unchanged.
Goal Enforcement: The goal state must be enforced by constraints, not imposed as a fact, to allow the solver to find a plan that achieves the goal.
Iterative Solving: Planning problems are often solved by iteratively calling an ASP solver with increasing time horizons until a solution is found.
Complexity: The complexity of planning problems often exceeds NP, frequently suggesting PSPACE-completeness, which indicates a higher level of computational difficulty.

Follow-up Questions and Topics for Next Lecture: The following questions and topics will guide our exploration of more advanced concepts in planning and automated reasoning in the next lecture:

Optimization: How can we optimize the search for solutions in planning problems to find more efficient plans?
Uncertainty: What are some techniques for handling uncertainty in initial states or action effects, such as probabilistic planning?
Multi-Agent Planning: How can we extend these models to multi-agent planning scenarios, where multiple agents interact to achieve a common goal?
Relationship with Reinforcement Learning: What is the relationship between planning and other AI techniques like reinforcement learning, and how can they be combined?
General Frameworks: Can we develop a general framework or language for modeling a wider range of planning problems? (Introduction to PDDL)
Plan Optimality: Explore the concept of plan optimality beyond just the number of steps. Can we incorporate costs or preferences into our models?
Inertia Encoding: Investigate how different encodings of inertia rules can impact solver performance and scalability.
Automatic Encoding Generation: Discuss methods for automatically generating ASP encodings from high-level problem descriptions to reduce manual coding efforts.
Practical Limitations: Examine the practical limitations of using ASP for large-scale planning problems and potential solutions to address these limitations.
Hierarchical Planning: Introduce the concept of hierarchical planning and its advantages in managing complex planning tasks.

These questions will serve as a starting point for our next discussion, where we will delve deeper into advanced planning techniques and their applications.

--- title: "Introduction to Planning Problems in AI" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction {#sec:introduction} This document provides a comprehensive overview of planning problems in Artificial Intelligence (AI), with a particular emphasis on modeling these problems using Answer Set Programming (ASP). We will delve into several classic examples, including the [Wolf, Goat, and Cabbage problem](#sec:wolf_goat_cabbage), the [Wine Barrel problem](#sec:wine_barrel), the [Towers of Hanoi](#sec:towers_hanoi), and the [15-Puzzle](#sec:15_puzzle). These examples will serve to illustrate fundamental concepts such as: - **Time Representation**: How to model the temporal aspect of planning problems. - **Action Preconditions and Effects**: Defining the conditions necessary for an action to occur and its consequences. - **Inertia Rules**: Specifying what remains unchanged when an action is performed. - **Complexity**: Understanding the distinction between NP-complete and PSPACE-complete problems in the context of planning. The primary objectives of this document are to: - Understand the process of modeling planning problems. - Learn how to represent time and actions within a formal framework. - Recognize the inherent complexity of planning problems and their implications. By the end of this document, readers should have a solid foundation in the core principles of planning in AI and be able to apply these principles to model and solve various planning challenges. # The Wolf, Goat, and Cabbage Problem {#sec:wolf_goat_cabbage} ## Problem Description {#subsec:wgc_description} The classic Wolf, Goat, and Cabbage problem involves a man who needs to transport a wolf, a goat, and a cabbage across a river. He has a small boat that can only carry himself and one other item at a time. The constraints are that the wolf cannot be left alone with the goat, and the goat cannot be left alone with the cabbage. The objective is to find a sequence of actions (a plan) that safely transports all items to the other side of the river. This problem is a fundamental example of a planning problem that requires reasoning about state transitions and constraints. ## Modeling the Problem {#subsec:wgc_modeling} To model this problem, we use a discrete notion of time and define the following: - **Time**: $t \in \{0, 1, ..., n\}$, where $n$ represents the unknown number of time steps required to solve the problem. - **Places**: The possible locations are the left bank, the right bank, and the boat. - **Objects**: The items to be transported are the man, the wolf, the goat, and the cabbage. :::: tcolorbox ::: {.def:wgc_state .definition} **Definition 1** (State). *A state at any time $t$ is defined by the location $p$ of each object $o$. We represent this with the predicate $on(t, o, p)$, indicating that object $o$ is at place $p$ at time $t$.* ::: :::: ## Initial State {#subsec:wgc_initial_state} At the initial time $t=0$, all objects are on the left bank of the river: - $on(0, \text{Man}, \text{Left})$ - $on(0, \text{Wolf}, \text{Left})$ - $on(0, \text{Goat}, \text{Left})$ - $on(0, \text{Cabbage}, \text{Left})$ ## Constraints {#subsec:wgc_constraints} The problem constraints are: - The wolf and goat cannot be left alone together: $$\label{eq:wgc_constraint_1} \forall t, p: on(t, \text{Goat}, p) \land on(t, \text{Cabbage}, p) \rightarrow on(t, \text{Man}, p)$$ This constraint ensures that if both the goat and the cabbage are in the same place at time $t$, the man must also be present. - The goat and cabbage cannot be left alone together: $$\label{eq:wgc_constraint_2} \forall t, p: on(t, \text{Wolf}, p) \land on(t, \text{Goat}, p) \rightarrow on(t, \text{Man}, p)$$ This constraint ensures that if both the wolf and the goat are in the same place at time $t$, the man must also be present. - The boat can carry at most two objects (including the man): $$\label{eq:wgc_constraint_3} \forall t: 0 \leq \sum_{o} on(t, o, \text{Boat}) \leq 2$$ This constraint limits the capacity of the boat to a maximum of two objects at any given time $t$. ## Action Effects {#subsec:wgc_action_effects} The effects of moving an object using the boat are modeled as follows: - If an object is on the left bank at time $t$ and on the boat at time $t+1$, it will be on the right bank at time $t+2$: $$\label{eq:wgc_action_effect_1} \forall t, o: on(t, o, \text{Left}) \land on(t+1, o, \text{Boat}) \rightarrow on(t+2, o, \text{Right})$$ This rule describes the transition of an object from the left bank to the right bank after being on the boat. - Similarly, if an object is on the right bank at time $t$ and on the boat at time $t+1$, it will be on the left bank at time $t+2$: $$\label{eq:wgc_action_effect_2} \forall t, o: on(t, o, \text{Right}) \land on(t+1, o, \text{Boat}) \rightarrow on(t+2, o, \text{Left})$$ This rule describes the transition of an object from the right bank to the left bank after being on the boat. - If an object is on the boat at time $t$, the man must also be on the boat: $$\label{eq:wgc_action_effect_3} \forall t, o: on(t, o, \text{Boat}) \rightarrow on(t, \text{Man}, \text{Boat})$$ This rule ensures that the man is always present in the boat when any other object is being transported. ## Inertia Rules {#subsec:wgc_inertia} Inertia rules specify that objects not involved in an action remain in their previous state. In this case, it is sufficient to state that objects cannot jump directly from the left bank to the right bank or vice versa: $$\begin{aligned} \label{eq:wgc_inertia_1} \forall t, o: \neg (on(t, o, \text{Left}) \land on(t+1, o, \text{Right})) \\ \label{eq:wgc_inertia_2} \forall t, o: \neg (on(t, o, \text{Right}) \land on(t+1, o, \text{Left}))\end{aligned}$$ These rules prevent objects from changing their location without using the boat. ## Goal State {#subsec:wgc_goal_state} The goal is to have all objects on the right bank at time $n$: $$\label{eq:wgc_goal_state} \text{Final} \leftarrow on(n, \text{Man}, \text{Right}) \land on(n, \text{Wolf}, \text{Right}) \land on(n, \text{Goat}, \text{Right}) \land on(n, \text{Cabbage}, \text{Right})$$ To ensure that the solver reaches the goal, we add a constraint that states that it is impossible not to reach the final state: $$\label{eq:wgc_goal_enforce} \neg \text{Final} \rightarrow \text{False}$$ ## ASP Code {#subsec:wgc_asp_code} The following ASP code encodes the Wolf, Goat, and Cabbage problem: ::: tcolorbox % Define time, places, and objects time(0..n). place(left). place(right). place(boat). object(man). object(wolf). object(goat). object(cabbage). % Initial state on(0, man, left). on(0, wolf, left). on(0, goat, left). on(0, cabbage, left). % Constraints on(T, man, P) :- time(T), place(P), on(T, goat, P), on(T, cabbage, P). on(T, man, P) :- time(T), place(P), on(T, wolf, P), on(T, goat, P). 0 { on(T, O, boat) : object(O) } 2 :- time(T). % Action effects on(T+2, O, right) :- on(T, O, left), on(T+1, O, boat), time(T), time(T+2). on(T+2, O, left) :- on(T, O, right), on(T+1, O, boat), time(T), time(T+2). on(T, man, boat) :- on(T, O, boat), object(O), time(T). % Inertia rules :- on(T, O, left), on(T+1, O, right), time(T), time(T+1), object(O). :- on(T, O, right), on(T+1, O, left), time(T), time(T+1), object(O). % Goal state final :- on(n, man, right), on(n, wolf, right), on(n, goat, right), on(n, cabbage, right). :- not final. % Define the action of moving onto the boat moved(T, O, From, To) :- on(T, O, From), on(T+1, O, To), From != To. % Ensure there is always an action :- not moved(T, O, From, To), time(T), T < n. % Show the moves #show moved/4. ::: ## Solving the Problem {#subsec:wgc_solving} The problem is solved by iteratively calling an ASP solver with increasing values of $n$ until a solution is found. The minimum $n$ for which a solution is found represents the shortest plan to move all objects to the right bank. This iterative approach is necessary because the length of the plan is not known in advance. The solver explores the space of possible actions and states, guided by the constraints and rules defined in the ASP code. # The Wine Barrel Problem {#sec:wine_barrel} ## Problem Description {#subsec:wb_description} The Wine Barrel problem involves three barrels with capacities of 12, 7, and 5 liters. Initially, the 12-liter barrel is full of wine, while the 7-liter and 5-liter barrels are empty. The objective is to reach a state where the 12-liter and 7-liter barrels each contain exactly 6 liters of wine, and the 5-liter barrel is empty. The only allowed action is to pour wine from one barrel to another until either the source barrel is empty or the destination barrel is full. This problem highlights the challenge of achieving a specific distribution of resources through a sequence of constrained actions. ## Modeling the Problem {#subsec:wb_modeling} To model this problem, we define the following: - **Time**: $t \in \{0, 1, ..., n\}$, where $n$ is the unknown number of steps. - **Barrels**: $b \in \{5, 7, 12\}$, representing the three barrels with their respective capacities. - **Amount**: $a \in \{0, 1, ..., 12\}$, representing the possible integer amounts of wine in liters that a barrel can contain. :::: tcolorbox ::: {.def:wb_state .definition} **Definition 2** (State). *A state at any time $t$ is defined by the amount $a$ of wine in each barrel $b$. We represent this with the predicate $contains(t, b, a)$, indicating that barrel $b$ contains $a$ liters of wine at time $t$.* ::: :::: ## Actions {#subsec:wb_actions} At each time step $t$, we can pour wine from barrel $x$ to barrel $y$, where $x \neq y$. This action is represented by the predicate $pour(t, x, y)$. There are six possible actions: - $pour(t, 12, 7)$ - $pour(t, 12, 5)$ - $pour(t, 7, 12)$ - $pour(t, 7, 5)$ - $pour(t, 5, 12)$ - $pour(t, 5, 7)$ We enforce that exactly one action occurs at each time step: $$\label{eq:wb_action_constraint} \forall t: \sum_{x, y, x \neq y} pour(t, x, y) = 1$$ ## Initial State {#subsec:wb_initial_state} The initial state at time $t=0$ is: - $contains(0, 12, 12)$ - $contains(0, 7, 0)$ - $contains(0, 5, 0)$ ## Goal State {#subsec:wb_goal_state} The goal state is defined as: - $contains(n, 12, 6)$ - $contains(n, 7, 6)$ - $contains(n, 5, 0)$ We enforce the goal state by defining the predicate `final` and ensuring that it is reached: $$\begin{aligned} \label{eq:wb_goal_state_def} \text{Final} &\leftarrow contains(n, 12, 6) \land contains(n, 7, 6) \land contains(n, 5, 0) \\ \label{eq:wb_goal_state_enforce} \neg \text{Final} &\rightarrow \text{False}\end{aligned}$$ ## Action Preconditions and Effects {#subsec:wb_action_effects} - **Precondition**: We cannot pour from an empty barrel or into a full barrel. - **Effect**: If we pour from barrel $x$ to barrel $y$ at time $t$, there are two cases: 1. If the amount in $x$ ($LX$) is less than or equal to the remaining capacity in $y$ ($Y - LY$), then $x$ becomes empty, and $y$ contains the sum of the amounts ($LX + LY$). 2. If the amount in $x$ ($LX$) is greater than the remaining capacity in $y$ ($Y - LY$), then $y$ becomes full, and $x$ contains the remaining amount ($LX - (Y - LY)$). ## Inertia Rules {#subsec:wb_inertia} The barrel not involved in the pouring action retains its amount of wine. This is modeled by ensuring that if a barrel $B$ is not the source ($X$) or destination ($Y$) of a pour action, its content remains unchanged between time $T$ and $T+1$. ## ASP Code {#subsec:wb_asp_code} The following ASP code encodes the Wine Barrel problem: ::: tcolorbox % Define time, barrels, and amounts time(0..n). barrel(5). barrel(7). barrel(12). amount(0..12). % Actions 1 { pour(T, X, Y) : barrel(X), barrel(Y), X != Y } 1 :- time(T), T < n. % Initial state contains(0, 12, 12). contains(0, 7, 0). contains(0, 5, 0). % Goal state final :- contains(n, 12, 6), contains(n, 7, 6), contains(n, 5, 0). :- not final. % Action preconditions :- pour(T, X, Y), contains(T, X, 0). :- pour(T, X, Y), contains(T, Y, Y). % Action effects contains(T+1, X, 0) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY >= LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY). contains(T+1, Y, LX + LY) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY >= LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY). contains(T+1, X, LX - (Y - LY)) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY < LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY). contains(T+1, Y, Y) :- pour(T, X, Y), contains(T, X, LX), contains(T, Y, LY), Y - LY < LX, time(T), time(T+1), barrel(X), barrel(Y), X != Y, amount(LX), amount(LY). % Inertia rules contains(T+1, B, A) :- pour(T, X, Y), contains(T, B, A), barrel(B), B != X, B != Y, time(T), time(T+1), amount(A). % Show the actions #show pour/3. ::: # The Towers of Hanoi {#sec:towers_hanoi} ## Problem Description {#subsec:toh_description} The Towers of Hanoi is a classic mathematical puzzle involving $N$ disks of different sizes and three pegs. Initially, all disks are stacked on one peg in decreasing order of size, forming a tower. The objective is to move the entire tower to another peg, adhering to the following rules: - Only one disk can be moved at a time. - A disk can only be moved if it is the topmost disk on a peg. - A larger disk cannot be placed on top of a smaller disk. This problem is often used to illustrate recursion and algorithmic problem-solving. ## Modeling the Problem {#subsec:toh_modeling} To model the Towers of Hanoi problem, we define: - **Time**: $t \in \{0, 1, ..., n\}$, where $n$ is the unknown number of steps. - **Pegs**: $p \in \{1, 2, 3\}$, representing the three pegs. - **Disks**: $d \in \{1, 2, ..., N\}$, representing the $N$ disks, where 1 is the smallest and $N$ is the largest. :::: tcolorbox ::: {.def:toh_state .definition} **Definition 3** (State). *A state at any time $t$ is defined by the position of each disk $d$ on a peg $p$. We represent this with the predicate $in(t, d, p)$, indicating that disk $d$ is on peg $p$ at time $t$. Additionally, we define a predicate $on(t, d_1, d_2)$ to indicate that disk $d_1$ is directly on top of disk $d_2$ at time $t$.* ::: :::: ## Actions {#subsec:toh_actions} At each time step $t$, we can move the top disk from peg $x$ to peg $y$, where $x \neq y$. This action is represented by the predicate $move(t, x, y)$. There are six possible actions: - $move(t, 1, 2)$ - $move(t, 1, 3)$ - $move(t, 2, 1)$ - $move(t, 2, 3)$ - $move(t, 3, 1)$ - $move(t, 3, 2)$ We enforce that exactly one action occurs at each time step: $$\label{eq:toh_action_constraint} \forall t: \sum_{x, y, x \neq y} move(t, x, y) = 1$$ ## Initial State {#subsec:toh_initial_state} Initially, all disks are on peg 1, stacked in decreasing order of size: - $in(0, d, 1)$ for all $d \in \{1, 2, ..., N\}$ - $on(0, d, d+1)$ for all $d \in \{1, 2, ..., N-1\}$ - $on(0, N, \text{floor})$, where `floor` represents the base of the peg. ## Goal State {#subsec:toh_goal_state} The goal state is to have all disks on peg 2, stacked in decreasing order of size: - $in(n, d, 2)$ for all $d \in \{1, 2, ..., N\}$ - $on(n, d, d+1)$ for all $d \in \{1, 2, ..., N-1\}$ - $on(n, N, \text{floor})$ The goal is reached when all disks are on peg 2 in the correct order. ## Action Preconditions and Effects {#subsec:toh_action_effects} - **Precondition**: We cannot move from an empty peg or place a larger disk on a smaller one. - **Effect**: If we move from peg $x$ to peg $y$ at time $t$, the top disk of peg $x$ is moved to the top of peg $y$. ## Inertia Rules {#subsec:toh_inertia} Disks not involved in the move action retain their positions. This is ensured by specifying that if a disk has not been moved, its position and the disk it is on top of remain the same. ## ASP Code (by Martin Gebser) {#subsec:toh_asp_code} The following ASP code, originally developed by Martin Gebser, encodes the Towers of Hanoi problem: ::: tcolorbox % Define time, pegs, and disks time(0..n). peg(1..3). disk(1..N). % Actions 1 { move(T, X, Y) : peg(X), peg(Y), X != Y } 1 :- time(T), T < n. % Initial state in(0, D, 1) :- disk(D). on(0, D, D+1) :- disk(D), D < N. on(0, N, floor). % Goal state goal :- in(n, D, 2) : disk(D). :- not goal. % Auxiliary predicates covered(T, D2) :- on(T, D1, D2), disk(D1), disk(D2). top(T, A, D) :- in(T, D, A), not covered(T, D). empty(T, A) :- peg(A), not in(T, D, A) : disk(D). top(T, A, floor) :- empty(T, A). moved_disk(T, D) :- move(T, A, B), top(T, A, D). % Action preconditions :- move(T, A, B), empty(T, A). :- on(T, D1, D2), D1 >= D2. % Action effects on(T+1, D1, D2) :- move(T, A, B), top(T, A, D1), top(T, B, D2). in(T+1, D, B) :- move(T, A, B), top(T, A, D). % Inertia rules on(T+1, D1, D2) :- on(T, D1, D2), not moved_disk(T, D1). in(T+1, D, A) :- in(T, D, A), not moved_disk(T, D). % Show the moves #show move/3. ::: # The 15-Puzzle {#sec:15_puzzle} ## Problem Description {#subsec:15p_description} The 15-Puzzle is a sliding puzzle consisting of a 4x4 grid with 15 numbered tiles and one empty space. The tiles are initially arranged in a scrambled order, and the goal is to arrange them in numerical order by sliding tiles into the empty space. This puzzle is a classic example of a problem that can be solved using planning techniques, requiring a sequence of moves to reach the desired configuration. ## Modeling the Problem {#subsec:15p_modeling} To model the 15-Puzzle, we define the following: - **Time**: $t \in \{0, 1, ..., n\}$, where $n$ is the unknown number of steps. - **Rows**: $r \in \{0, 1, 2, 3\}$, representing the rows of the grid. - **Columns**: $c \in \{0, 1, 2, 3\}$, representing the columns of the grid. - **Values**: $v \in \{0, 1, ..., 15\}$, representing the values of the tiles, where 0 represents the empty space. :::: tcolorbox ::: {.def:15p_state .definition} **Definition 4** (State). *A state at any time $t$ is defined by the value $v$ at each position $(r, c)$. We represent this with the predicate $cell(t, r, c, v)$, indicating that the cell at row $r$ and column $c$ contains value $v$ at time $t$.* ::: :::: ## Actions {#subsec:15p_actions} At each time step $t$, we can move the empty space (represented by the value 0) up, down, left, or right. This is equivalent to sliding a tile into the empty space. We represent this with the predicate $move(t, d)$, where $d \in \{\text{up}, \text{down}, \text{left}, \text{right}\}$. We enforce that exactly one action occurs at each time step: $$\label{eq:15p_action_constraint} \forall t: \sum_{d} move(t, d) = 1$$ ## Initial State {#subsec:15p_initial_state} The initial state is given by the specific arrangement of tiles. For example, a possible initial state is: - $cell(0, 0, 0, 1)$ - $cell(0, 0, 1, 2)$ - $cell(0, 0, 2, 3)$ - $cell(0, 0, 3, 4)$ - $cell(0, 1, 0, 5)$ - $cell(0, 1, 1, 6)$ - $cell(0, 1, 2, 7)$ - $cell(0, 1, 3, 8)$ - $cell(0, 2, 0, 9)$ - $cell(0, 2, 1, 10)$ - $cell(0, 2, 2, 11)$ - $cell(0, 2, 3, 12)$ - $cell(0, 3, 0, 13)$ - $cell(0, 3, 1, 14)$ - $cell(0, 3, 2, 15)$ - $cell(0, 3, 3, 0)$ ## Goal State {#subsec:15p_goal_state} The goal state is to have the tiles arranged in numerical order, with the empty space in the bottom-right corner: $$\begin{aligned} \label{eq:15p_goal_state_def_1} \text{Final} &\leftarrow cell(n, r, c, 4r + c + 1) \text{ for } r, c \in \{0, 1, 2, 3\}, (r, c) \neq (3, 3) \\ \label{eq:15p_goal_state_def_2} \text{Final} &\leftarrow cell(n, 3, 3, 0)\end{aligned}$$ We enforce the goal state by adding the constraint: $$\label{eq:15p_goal_state_enforce} \neg \text{Final} \rightarrow \text{False}$$ ## Action Preconditions and Effects {#subsec:15p_action_effects} - **Precondition**: We cannot move the empty space outside the grid. - **Effect**: If we move the empty space in direction $d$ at time $t$, the empty space and the adjacent tile in that direction swap positions. ## Inertia Rules {#subsec:15p_inertia} Tiles not involved in the move action retain their positions. This is ensured by specifying that if a cell's value is not changed by a move action, it remains the same in the next time step. ## ASP Code {#subsec:15p_asp_code} The following ASP code encodes the 15-Puzzle problem: ::: tcolorbox % Define time, rows, columns, and values time(0..n). row(0..3). col(0..3). value(0..15). % Actions 1 { move(T, up); move(T, down); move; move(T, left); move(T, right) } 1 :- time(T), T < n. % Initial state (example) cell(0, 0, 0, 1). cell(0, 0, 1, 2). cell(0, 0, 2, 3). cell(0, 0, 3, 4). cell(0, 1, 0, 5). cell(0, 1, 1, 6). cell(0, 1, 2, 7). cell(0, 1, 3, 8). cell(0, 2, 0, 9). cell(0, 2, 1, 10). cell(0, 2, 2, 11). cell(0, 2, 3, 12). cell(0, 3, 0, 13). cell(0, 3, 1, 14). cell(0, 3, 2, 15). cell(0, 3, 3, 0). % Goal state final :- cell(n, R, C, R * 4 + C + 1) : row(R), col(C), (R, C) != (3, 3), cell(n, 3, 3, 0). :- not final. % Action preconditions :- move(T, up), cell(T, 0, C, 0). :- move(T, down), cell(T, 3, C, 0). :- move(T, left), cell(T, R, 0, 0). :- move(T, right), cell(T, R, 3, 0). % Action effects cell(T+1, R-1, C, 0) :- move(T, up), cell(T, R, C, 0), row(R), R > 0. cell(T+1, R+1, C, 0) :- move(T, down), cell(T, R, C, 0), row(R), R < 3. cell(T+1, R, C-1, 0) :- move(T, left), cell(T, R, C, 0), col(C), C > 0. cell(T+1, R, C+1, 0) :- move(T, right), cell(T, R, C, 0), col(C), C < 3. cell(T+1, R, C, V) :- move(T, up), cell(T, R, C, 0), cell(T, R-1, C, V), V != 0, row(R), R > 0. cell(T+1, R, C, V) :- move(T, down), cell(T, R, C, 0), cell(T, R+1, C, V), V != 0, row(R), R < 3. cell(T+1, R, C, V) :- move(T, left), cell(T, R, C, 0), cell(T, R, C-1, V), V != 0, col(C), C > 0. cell(T+1, R, C, V) :- move(T, right), cell(T, R, C, 0), cell(T, R, C+1, V), V != 0, col(C), C < 3. % Inertia rules cell(T+1, R, C, V) :- cell(T, R, C, V), not cell(T+1, R, C, 0), V != 0. % Show the moves #show move/2. ::: # Conclusion {#sec:conclusion} In this lecture, we have explored several classic planning problems and their representation using Answer Set Programming (ASP). We have emphasized the importance of: - Modeling time as a discrete sequence of steps. - Defining actions with clear preconditions and effects. - Implementing inertia rules to specify what remains unchanged when an action is performed. - Enforcing the goal state, rather than imposing it as a given fact. We have also highlighted the distinction between NP-complete and PSPACE-complete problems, noting that many planning problems, due to their inherent complexity, often fall into the latter category. ::: tcolorbox The key takeaways from this lecture are: - **Planning Problems**: Involve finding a sequence of actions to reach a desired goal state. - **Discrete Time**: Time can be discretized and represented as a parameter in predicates, allowing for modeling of temporal sequences. - **Action Modeling**: Actions have preconditions that must be met for them to be executed and effects that describe the resulting changes in the state. - **Inertia Rules**: Specify that objects or properties not directly affected by an action remain unchanged. - **Goal Enforcement**: The goal state must be enforced by constraints, not imposed as a fact, to allow the solver to find a plan that achieves the goal. - **Iterative Solving**: Planning problems are often solved by iteratively calling an ASP solver with increasing time horizons until a solution is found. - **Complexity**: The complexity of planning problems often exceeds NP, frequently suggesting PSPACE-completeness, which indicates a higher level of computational difficulty. ::: **Follow-up Questions and Topics for Next Lecture:** The following questions and topics will guide our exploration of more advanced concepts in planning and automated reasoning in the next lecture: - **Optimization**: How can we optimize the search for solutions in planning problems to find more efficient plans? - **Uncertainty**: What are some techniques for handling uncertainty in initial states or action effects, such as probabilistic planning? - **Multi-Agent Planning**: How can we extend these models to multi-agent planning scenarios, where multiple agents interact to achieve a common goal? - **Relationship with Reinforcement Learning**: What is the relationship between planning and other AI techniques like reinforcement learning, and how can they be combined? - **General Frameworks**: Can we develop a general framework or language for modeling a wider range of planning problems? (Introduction to PDDL) - **Plan Optimality**: Explore the concept of plan optimality beyond just the number of steps. Can we incorporate costs or preferences into our models? - **Inertia Encoding**: Investigate how different encodings of inertia rules can impact solver performance and scalability. - **Automatic Encoding Generation**: Discuss methods for automatically generating ASP encodings from high-level problem descriptions to reduce manual coding efforts. - **Practical Limitations**: Examine the practical limitations of using ASP for large-scale planning problems and potential solutions to address these limitations. - **Hierarchical Planning**: Introduce the concept of hierarchical planning and its advantages in managing complex planning tasks. These questions will serve as a starting point for our next discussion, where we will delve deeper into advanced planning techniques and their applications.