From the previous two examples, it should be clear how to compute nondeterministic I-states and therefore solve the passive localization problem on a grid. Now consider constructing a plan that solves the active localization problem. Imagine using a computer to help in this task. There are two general approaches:
Using either approach, it will be helpful to recall the formulation of Section 12.1.1, which considers as a new state space, , in which state feedback can be used. Even though there are no nature sensing actions, the observations are not predictable because the state is generally unknown. This means that is unknown, and future new states, , are unpredictable once and are given. A plan must therefore use feedback, which means that it needs information learned during execution to solve the problem. The state transition function on the new state space was illustrated for the localization problem in Examples 12.1 and 12.2. The initial state is the set of all original states. If there are no symmetries, the goal set is the set of all singleton subsets of ; otherwise, it is the set of all smallest possible I-states that are reachable (this does not need to be constructed in advance). If desired, cost terms can be defined to produce an optimal planning problem. For example, if a motion occurs, or otherwise.
Consider the approach of precomputing a plan. The methods of Section 12.1.2 can generally be applied to compute a plan, , that solves the localization problem from any initial nondeterministic I-state. The approach may be space-intensive because an action must be stored for every state in . If there are grid tiles, then . If the initial I-state is always , then it may be possible to restrict to a much smaller portion of . From any , a search based on backprojections can be conducted. If the initial I-state is added to , then the partial plan will reliably localize the robot. Parts of for which is not specified will never be reached and can therefore be ignored.
Now consider the lazy approach. An algorithm running on the robot can perform a kind of search by executing actions and seeing which I-states result. This leads to a directed graph over that is incrementally revealed through the robot's motions. The graph is directed because the information regarding the state generally improves. For example, once the robot knows its state (or symmetry class of states), it cannot return to an I-state that represents greater uncertainty. In many cases, the robot may get lucky during execution and localize itself using much less memory than would be required for a precomputed plan.
The robot needs to recognize that the same positions have been reached in different ways, to ensure a systematic search. Even though the robot does not necessarily know its position on the map, it can usually deduce whether it has been to some location previously. One way to achieve this is to assign coordinates to the positions already visited. It starts with assigned to the initial position. If is applied, then suppose that position is reached, assuming the robot moves to a new grid cell. If is applied, then is reached if the robot is not blocked. The point may be reachable by or . One way to interpret this is that a local coordinate frame in is attached to the robot's initial position. Let this be referred to as the odometric coordinates. The orientation between this coordinate frame and the map is not known in the beginning, but a transformation between the two can be computed if the robot is able to localize itself exactly.
A variety of search algorithms can now be defined by starting in the initial state and trying actions until a goal condition is satisfied (e.g., no smaller nondeterministic I-states are reachable). There is, however, a key difference between this search and the search conducted by the algorithms in Section 2.2.1. Previously, the search could continue from any state that has been explored previously without any additional cost. In the current setting, there are two issues:
Steven M LaValle 2012-04-20