Planning

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

See Path Planning for more specifics?

Introduction

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$.
^1634612340506

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

• The set of vertices is the state space $X$.
• A directed edge from $x\in X$ to $x\prime \in X$ exists in the graph if and only if there exists an action $u\in U(x)$ such that $x\prime =f(x,u)$.
• The initial state and goal set are designated as special vertices in the graph.

Examples

Moving on a 2D Grid

• Suppose that a robot moves on a grid in which each grid point has integer coordinates of the form $(i,j)$. 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 $X$ be the set of all integer pairs of the form $(i,j)$, in which $i,j\in \mathbb{Z}$.

  2. Let $U=(0,1),(0,-1),(1,0),(-1,0)$. Let $U(x)=U$ for all $x\in X$.

  3. The state transition equation is $f(x,u)=x+u$, in which $x\in X$ and $u\in U$ are treated as two-dimensional vectors for the purpose of addition. For example, if $x=(3,4)$ and $u=(0,1)$, then $f(x,u)=(3,5)$.

  4. Suppose for convenience that the initial state is $x_I=(0,0)$.

  5. Many interesting goal sets are possible. Suppose, for example, that $X_G=(100,100)$.

  • It is easy to find a sequence of actions that transforms the state from $(0,0)$ to $(100,100)$.
  • We can make the problem more interesting by adding obstacles and fences so that $X$ 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.

Related:#idontunderstand

• Finite State Machine
• Deterministic Finite Automaton

General Forward Search

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 $x_I$.
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 $x_I$.

• Breadth-First Search
• Depth-First Search
• Dijkstra’s Algorithm
• A-Star Algorithm
• Best-First Search
• Iterative Deepening
• Backward Search
• Bidirectional Search

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, $G(V,E)$, be initialized with $E$ empty and $V$ containing some starting states. For forward search, $V=x_I$; for backward search, $V=\{x_G\}$. If bidirectional search is used, then $V=\{x_I,x_G\}$. 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 $V$. The search graph will incrementally grow to reveal more and more of the state transition graph.
2. Select Vertex: Choose a vertex $n_{cur}\in V$ for expansion; this is usually accomplished by maintaining a priority queue. Let $x_{cur}$ denote the state associated with $n_{cur}$.
3. Apply an Action: In either a forward or backward direction, a new state, $x_{new}$, is obtained. This may arise from $x_{new}=f(x,u)$ for some $u\in U(x)$ (forward) or $x=f(x_{new},u)$ for some $u\in U(x_{new})$ (backward).
4. Insert a Directed Edge into the Graph: If certain algorithm-specific tests are passed, then generate an edge from $x$ to $x_{new}$ for the forward case,or an edge from $x_{new}$ to $x$ for the backward case. If $x_{new}$ is not yet in $V$ , it will be inserted into $V$ .
5. Check for Solution: Determine whether $G$ encodes a path from $x_I$ to $x_G$. 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.