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.