Many algorithms have been developed to compute backprojections. The first algorithm was given in [311,312]. Assume that the goal region is one or more segments contained in edges of . The algorithm proceeds for a fixed motion command, , which is based on a direction as follows:
Once an algorithm that computes backprojections has been obtained, it needs to be adapted to compute preimages. Using the sensing model shown in Figure 12.45b, a preimage can be obtained by shrinking the subgoal region . Let denote the radius of the ball in Figure 12.45b. Let denote a subset of the subgoal in which a strip of thickness has been removed. If the sensor returns , then it is guaranteed that . This yields a method of obtaining preimages by shrinking the subgoals. If is too large, however, this may fail to yield a successful plan, even though one exists.
The high-level plan can be found by performing a backward search that computes backprojections from the goal region (reduced by ). There is still the difficulty of being too large, which controls the branching factor in the search. One possibility is to compute nondirectional backprojections. Another possibility is to discretize . For example, in [588,590], is reduced to four principle directions, and plans are computed for complicated environments by using sticking edges as subgoals. Using discretization, however, it becomes more difficult to ensure the completeness of the planning algorithm.
The preimage planning framework may seem to apply only to a very specific model, but it can be extended and adapted to a much more general setting. It was extended to semi-algebraic obstacle models in , which gives a planning method that runs in time doubly exponential in the C-space dimension (based on cylindrical algebraic decomposition, which was covered in Section 6.4.2). In , probabilistic backprojections were introduced by assigning a uniform probability density function to the nature action spaces considered in this section. This was in turn generalized further to define backprojections and preimages as the level sets of optimal cost-to-go functions in [597,605]. Dynamic programming methods can then be applied to compute plans.
Steven M LaValle 2012-04-20