Deliberative control is historically the oldest method to control robots. The prominent case is Shakey, developed at the Artificial Intelligence Center of the Stanford Research Institute — the project started in 1966 (Chapter 2 dated it). It is based on a symbolic representation of the robot and the world, and on formal reasoning for deciding the actions the robot takes.
The SPA architecture is the direct descendant of the AI tradition of Chapter 2: Shakey's STRIPS planner (Chapter 14) is the archetype. Chapter 4 already classified it as the deliberative end of the spectrum; this chapter fills in the machinery.
The crucial part of the SPA architecture is planning:
Planning is the process of looking ahead at the outcomes of the possible actions, and searching for the sequence of actions that will reach the desired goal. Planning is one of the most developed and advanced areas in AI; besides general principles, there are many specific planning techniques depending on the application.
Chapter 4's decision questions are now concrete: deliberation buys generality, optimality and verifiability, and pays with the assumption that the world model is accurate and up to date — exactly the assumption that noise, change and partial observability break. Questions 7–9 of Chapter 4 (is there too much state? is the world too fast? are the sensors too weak?) are the filter that decides whether the SPA architecture is usable at all.
Navigation refers to the problem of moving a robot to a given destination. In general this problem involves building a map of the environment, localizing both the robot and the target (if its location is known...), finding a proper sequence of moves to apply, and providing the right signals to the actuators.
Components of the navigation problem:
Localization is the process of figuring out where you (the robot) are, relatively to some model of the environment and using whatever sensor measurements are available. It requires continuous computation, as the robot keeps moving and its estimated position is likely to change in time. It can be achieved by means of systems such as:
Odometry's accumulating error is the same lesson as Chapter 1's situatedness: the robot only has its readings, and readings that integrate over time drift. Every navigation system is a story about how the drift is corrected — by absolute references (GPS, landmarks) or by closing loops (SLAM).
The problem: you have a map of a territory and you want to program a robot such that, given a starting and a goal position (S, G), it can compute a trajectory (possibly the shortest, or the quickest, or the cheapest one, or...) and move from S to G. An abstraction may help: (1) superimpose a grid over the map; (2) mark the cells depending on their features (obstacle, rough terrain, etc.). Assume the robot's moves are abstract discrete movements between cells (e.g. NORTH, SOUTH, EAST, WEST); a subsequent refinement will translate these moves into actual motor controls. Now the problem is to find a sequence of abstract moves connecting S to G.
Generalising: the problem is defined in terms of states and actions that connect two states; possibly actions have a cost (moving on rough surface is more costly than on a smooth one); the robot may take an action from a given finite set and has to find a (optimal) sequence of actions that makes it possible to start from S and reach G. This problem definition captures not only path planning but also many other AI problems: they are commonly called search problems. The classic formulation (Russell & Norvig; the slides are a revised version of their additional material): a problem is defined by four items — the initial state, the successor function S(x) = set of action–state pairs, the goal test (explicit or implicit), and the (additive) path cost with step cost c(x, a, y) ≥ 0. A solution is a sequence of actions leading from the initial state to a goal state. Example: on holiday in Romania, in Arad, flight leaves tomorrow from Bucharest — formulate goal (be in Bucharest), formulate problem (states: cities; actions: drive between cities), find solution (Arad, Sibiu, Fagaras, Bucharest).
The real world is absurdly complex, so the state space must be abstracted for problem solving:
Example — the 8-puzzle: states = integer locations of tiles (ignoring intermediate positions); actions = move blank left, right, up, down (ignoring unjamming etc.); goal test = goal state (given); path cost = 1 per move. (The optimal solution of the n-Puzzle family is NP-hard.)
Basic idea: offline, simulated exploration of the state space, by generating successors of already-explored states (a.k.a. expanding states). A strategy is defined by the order of node expansion. Strategies are evaluated along four dimensions: completeness (does it always find a solution if one exists?), time complexity (number of nodes generated/expanded), space complexity (maximum number of nodes in memory), optimality (does it always find a least-cost solution?). Time and space complexity are measured in terms of b (maximum branching factor), d (depth of the least-cost solution), m (maximum depth of the state space, possibly ∞).
Uninformed strategies use only the information available in the problem definition.
| Strategy | Rule | Complete | Time | Space | Optimal |
|---|---|---|---|---|---|
| Breadth-first | Expand shallowest unexpanded node (fringe = FIFO) | Yes (if b finite) | O(bd) | O(bd) — keeps every node | Yes (if cost nondecreasing in depth) |
| Depth-first | Expand deepest unexpanded node (fringe = LIFO) | No (infinite-depth spaces, loops; complete in finite spaces if repeated states along path are avoided) | O(bm) — terrible if m ≫ d, but fast if solutions are dense | O(bm) — linear space! | No |
| Depth-limited | DFS with depth limit l | No if l < d | O(bl) | O(bl) | No |
| Iterative deepening | Depth-limited with l = 0, 1, 2, ... until success | Yes | O(bd) — (d+1)b0 + db1 + ... + bd | O(bd) | Yes (if step cost nondecreasing in depth) |
Chronological backtracking is a variant of DFS that generates successors one at a time, reducing space complexity to O(m). Iterative deepening search is the preferred uninformed strategy when the search space is large and the solution depth is not known.
The message of the table is the space/time tradeoff: BFS finds the shallowest solution but remembers everything; DFS remembers little but can wander forever. Iterative deepening gets BFS's optimality with DFS's linear space — at the price of re-expanding nodes many times. This is the first place in the course where "you cannot have it all" is quantified precisely; Chapter 4's "no best controller" is the same statement at the architecture level.
Informed strategies use heuristic information about the problem to choose the node to expand: use an evaluation function for each node — an estimate of "desirability" — and expand the most desirable unexpanded node (fringe = queue sorted in decreasing order of desirability). Notable cases: greedy search and A* search.
Click cells to toggle walls. Press "Plan" to run A* from the red start to the green goal with 4-neighbour moves. Cobalt cells were expanded (closed), soft cells are in the open set, the forest line is the path found.
RRTs are typically used to solve trajectory planning with differential constraints. The algorithm builds a graph of points randomly chosen in the neighbourhood and iteratively connected to the closest point of the graph; it stops when the target is in the neighbourhood of a node in the tree; it may also be bi-directional (grow from both start and goal). In the early iterations the RRT quickly reaches the unexplored parts; it is dense in the limit (with probability one), which means that it gets arbitrarily close to any point in the space. (Picture taken from LaValle, Planning Algorithms, 2006.)
The tree grows by sampling a random point, finding the nearest node, and extending toward the sample. Watch the early bias toward unexplored regions, then the tree refining the discovered corridor.
SLAM is a hard problem as it involves both localization and map building at the same time. It requires tackling the data association problem: uniquely associating the sensed data with absolute ground truth — in other words, the robot has to correctly identify landmarks. Several methods are available, such as those based on the Kalman filter.
Two basic versions: (1) with a map — basically a search problem with multiple targets, until either an object is found or all the area is covered; (2) without a map — heuristically solved (e.g. by following continuous boundaries, or moving in spirals, or — naively — moving randomly).
Deliberative control is historically the oldest method to control robots: it is based on a symbolic representation of the robot and the world and on formal reasoning for deciding the actions the robot takes. The prominent case is Shakey, developed at SRI starting in 1966. Its architecture is Sense–Plan–Act (SPA).
Planning is the process of looking ahead at the outcomes of the possible actions and searching for the sequence of actions that will reach the desired goal. Advantages: a specific sequence of actions is generated for any feasible task; the control program can be formally analysed and checked; high-level tasks can be accomplished; optimal plans w.r.t. merit factors (e.g. time) can be found.
Time-scale (planning might be too long for real-time operation); computational resources limits (search might be too complex for on-board resources); the planner assumes the representation of the world is accurate and up to date (often false); success depends on the precision of sensor readings and actuator effects; whatever is not formally represented might invalidate the plan (e.g. an unpredicted change in the world).
Navigation is the problem of moving a robot to a given destination: it involves building a map of the environment, localizing the robot and the target, finding a proper sequence of moves, and providing the right signals to the actuators. Components: localization, search, path planning, coverage, and simultaneous localization and mapping (SLAM).
Localization is figuring out where the robot is, relative to a model of the environment, using sensor measurements; it requires continuous computation as the robot moves. Achieved via GPS/indoor positioning, landmarks, or odometry (path integration). Odometry is usually severely affected by errors that accumulate in time, so it requires regular corrections.
A problem is defined by: initial state; successor function S(x) = set of action–state pairs; goal test (explicit or implicit); additive path cost with step cost c(x,a,y) ≥ 0. A solution is a sequence of actions from the initial state to a goal state. The state space must be abstracted because the real world is absurdly complex: abstract state = set of real states; abstract action = complex combination of real actions; abstract solution = set of real paths that are solutions; each abstract action should be easier than the original problem.
Completeness (does it always find a solution if one exists?), time complexity (nodes generated/expanded), space complexity (maximum nodes in memory), optimality (does it always find a least-cost solution?). b = maximum branching factor, d = depth of the least-cost solution, m = maximum depth of the state space (may be ∞).
BFS expands the shallowest node (FIFO): complete, O(b^d) time and space, optimal if cost nondecreasing in depth. DFS expands the deepest (LIFO): not complete in infinite spaces (complete in finite spaces if repeated states are avoided), O(b^m) time, O(bm) linear space, not optimal. Depth-limited: DFS with limit l; not complete if l < d. Iterative deepening: repeated depth-limited searches with l = 0,1,2,...: complete, O(b^d) time, O(bd) space, optimal if step cost nondecreasing in depth — the preferred uninformed strategy for large spaces with unknown solution depth.
Both are informed strategies using an evaluation function. Greedy expands the node that appears closest to the goal (evaluation h(n), e.g. straight-line distance): efficient but neither complete nor optimal. A* uses f(n) = g(n) + h(n) (cost so far + heuristic estimate): with an admissible heuristic (never overestimating the true cost) it is complete and optimal — it expands nodes in order of increasing f. A* and its variants are classical approaches to path planning; RRTs handle trajectory planning with differential constraints.
RRTs build a graph of points randomly chosen in the neighbourhood, iteratively connected to the closest point of the graph, stopping when the target is near a node; may be bi-directional. Early iterations quickly reach unexplored parts; the tree is dense in the limit (with probability one), so it gets arbitrarily close to any point in the space. Typically used for trajectory planning with differential constraints.
SLAM is simultaneous localization and mapping — a hard problem because it involves both localization and map building at once. It requires tackling the data association problem: uniquely associating the sensed data with absolute ground truth — the robot has to correctly identify landmarks. Several methods exist, such as those based on the Kalman filter.
(1) With a map: basically a search problem with multiple targets, until either an object is found or all the area is covered. (2) Without a map: heuristically solved, e.g. following continuous boundaries, moving in spirals, or naively moving randomly.