# 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

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.

#### 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 . 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.

Related:#idontunderstand

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.