12.5.1 Preimage Planning

The preimage planning framework (or LMT framework, named after its developers, Lozano-Pérez, Mason, and Taylor) was developed as a general way to perform manipulation planning under uncertainty [311,659]. Although the concepts apply to general configuration spaces, they will be covered here for the case in which $ {\cal C}= {\mathbb{R}}^2$ and $ {\cal C}_{obs}$ is polygonal. This is a common assumption throughout most of the work done within this framework. This could correspond to a simplified model of a robot hand that translates in $ {\cal W}= {\mathbb{R}}^2$, while possibly carrying a part. A popular illustrative task is the peg-in-hole problem, in which the part is a peg that must be inserted into a hole that is slightly larger. This operation is frequently performed as manufacturing robots assemble products. Using the configuration space representation of Section 4.3.2, the robot becomes a point moving in $ {\mathbb{R}}^2$ among polygonal obstacles.

The distinctive features of the models used in preimage planning are as follows:

  1. The robot can execute compliant motions, which means that it can slide along the boundary of $ {\cal C}_{obs}$. This differs from the usual requirement in Part II that the robot must avoid obstacles.
  2. There is nondeterministic uncertainty in prediction. An action determines a motion direction, but nature determines how much error will occur during execution. A bounded error model is assumed.
  3. There is nondeterministic uncertainty in sensing, and the true state cannot be reliably estimated.
  4. The goal region is usually an edge of $ {\cal C}_{obs}$, but it may more generally be any subset of $ \operatorname{cl}({\cal C}_{free})$, the closure of $ {\cal C}_{free}$.
  5. A hierarchical planning model is used, in which the robot is issued a sequence of motion commands, each of which is terminated by applying $ u_T$ based on the I-state.
Each of these will now be explained in more detail.

Steven M LaValle 2012-04-20