I think planning is a super interesting field to get into, that generalizes really well.

See Path Planning for more specifics?


The planning book is basically everything I want to know.

Outline: p. 5

Planning encompasses a lot of things. In robotics, we talking about motion planning and trajectory planning. Control theory could include mechanical systems such as cars or aircraft, electrical systems such as noise filters, or even systems arising in areas as diverse as chemistry, economics, and sociology. In artificial intelligence, there’s planning to solve a Rubik’s Cube or building a stack of blocks.

Basic Ingredients of Planning#card

  • State
  • Time
  • Actions
  • Initial and Goal states
  • A criterion
    • Feasibility
    • Optimality
  • A plan

Discrete Planning

Discrete Feasible Planning

title: Formulation 2.1 (Discrete Feasible Planning) #card
1. A nonempty *state space* $X$, which is a finite or countably infinite set of *states*. 
2. For each *state* $x \in X$, a finite *action space* $U(x)$. 
3. A *state transition function f* that produces a state $f(x, u) \in X$ for every $x \in X$ and $u \in U(x)$. The *state transition equation* is derived from $f$ as $xβ€² = f(x, u)$.
4. An *initial state* $x_I \in X$.
5. A *goal set* $X_G \subset X$.

Note: It is often convenient to express Formulation 2.1 as a directed state transition graph:

  • The set of vertices is the state space .
  • A directed edge from to exists in the graph if and only if there exists an action such that .
  • The initial state and goal set are designated as special vertices in the graph.


Moving on a 2D Grid

  • Suppose that a robot moves on a grid in which each grid point has integer coordinates of the form . The robot takes discrete steps in one of four directions (up, down, left, right), each of which increments or decrements one coordinate.
  • Using Formulation 2.1.:
    1. Let be the set of all integer pairs of the form , in which .

    2. Let . Let for all .

    3. The state transition equation is , in which and are treated as two-dimensional vectors for the purpose of addition. For example, if and , then .

    4. Suppose for convenience that the initial state is .

    5. Many interesting goal sets are possible. Suppose, for example, that .

    • It is easy to find a sequence of actions that transforms the state from to .
    • We can make the problem more interesting by adding obstacles and fences so that becomes finite. Very complicated labyrinths can be constructed.

Oftentimes, we use a State Transition Graph to implementFormulation 2.1 directly, composed of vertices and edges.


These are basic graph search algorithms, but with the understanding that the state transition graph is revealed incrementally.

There are 3 Kinds of States

  1. Unvisited: States that have not been visited yet. Initially, this is every state except .
  2. Dead: States that have been visited, and for which every possible next state has also been visited.
  3. Alive: States that have been encountered, but possibly have unvisited next states. These are considered alive. Initially, the only alive state is .

2.2.4 A Unified View of the Search Methods

All of the planning methods from this section followed the same basic template:

  1. Initialization: Let the search graph, , be initialized with empty and containing some starting states. For forward search, ; for backward search, . If bidirectional search is used, then . It is possible to grow more than two trees and merge them during the search process. In this case, more states can be initialized in . The search graph will incrementally grow to reveal more and more of the state transition graph.
  2. Select Vertex: Choose a vertex for expansion; this is usually accomplished by maintaining a priority queue. Let denote the state associated with .
  3. Apply an Action: In either a forward or backward direction, a new state, , is obtained. This may arise from for some (forward) or for some (backward).
  4. Insert a Directed Edge into the Graph: If certain algorithm-specific tests are passed, then generate an edge from to for the forward case,or an edge from to for the backward case. If is not yet in , it will be inserted into .
  5. Check for Solution: Determine whether encodes a path from to . If there is a single search tree, then this is trivial. If there are two or more search trees, then this step could be expensive.
  6. Return to Step 2: Iterate unless a solution has been found or an early termination condition is satisfied, in which case the algorithm reports failure.

Discrete Optimal Planning

Rather than being satisfied with any sequence of actions that leads to the goal set, suppose we would like a solution that optimizes some criterion, such as time, distance, or energy consumed.

title:Formulation 2.2 (Discrete Fixed-Length Optimal Planning) 
1. All of the components from Formulation 2.1 are inherited directly: $X, U(x), f, x_I,$ and $X_G$, except here it is assumed that $X$ is finite (some algorithms may easily extend to the case in which $X$ is countably infinite, but this will not be considered here). 
2. A number, $K$, of *stages*, which is the exact length of a plan (measured as the number of actions,$u_1, u_2, \dots, u_K$). States may also obtain a stage index. For example, $x_{k+1}$ denotes the state obtained after uk is applied. 
3. Let L denote a stage-additive cost (or loss) functional, which is applied to a K-step plan, $\pi_K$. This means that the sequence ($u_1, u_2, \dots, u_K$) of actions and the sequence ($x_1, \dots, x_{K+1}$) of states may appear in an expression of L. For convenience, let $F$ denote the final stage, $F = K + 1$ (the application of $u_K$ advances the stage to $K + 1$). The *cost functional* is 
$$L(\pi_K) = \sum_{k=1}^K l(x_k, u_k) + l_F(x_F)$$
- The *cost term* $l(x_k, u_k)$ yields a real value for every $x_k \in X$ and $u_k \in U(x_k)$. 
- The *final term* $l_F(x_F)$ is outside of the sum and is defined as $l_F (x_F) = 0$ if $x_F \in X_G$, and $l_F(x_F) = \infty$ otherwise.