- A motion planner that incorporates heuristics, doing both greedy and methodical search
- Has completeness guarantees
- Domains of interest are non-holonomic systems w/2nd order constraints, such as a car with bounded acceleration and steering velocity
- Constructs paths that have a stable end state
- RRT requires a distance metric, but it may be difficult to define a good one for many domains, which severely impacts the quality of solutions
- There is another algorithm PDST that doesn’t require a distance metric and performs adaptive subdivision and is probabistically complete
- Both methods “can be viewed as continuous-space analogs of traditional uniformed search.”
- This paper proposes a method that performs informed search in state space
- Algorithm proposed is called
**Informed Subdivision Tree (IST)** - Algorithm operates in C-Space
- Say that operating in C-space can lead to getting stuck in local minima (I don’t know enough about the field to know why this is)
- In order to resolve the problem it uses the adaptive subdivision methods of PDST

- Builds a tree, everytime a random point is selected the tree subdivides the leaf that point corresponds to is subdivided
- Similar in concept to MRE, using the size of the leaf to determine how well known a region is
- Cells that have no connected points have an “exploration value” of ∞
- For some domains it is possible to do a projection to work in a smaller dimension problem. The car domain that was mentioned is one example
- They use a precomputed PRM to create a good heuristic for the planning space
- The heuristic function used is a product of a number of terms (such as distance to nearest obstacle), so its a little more expensive to query but empirically leads to more efficient planning
- There is also a penalty for repeatedly trying to plan from the same edge
- Trajectory libraries are used for planning to connect points
- There are many components to the paper and I’m only half paying attention because I am a displaced person at the moment
- Skipping completeness proof
- The planner is up to an order of magnitude faster than RRT-goal bias, RRT*, and PDST
- Paths formed are also of higher quality, which is attributed to the good heuristic function

- “Sampling-based kinodynamic planners are unable to solve some hard kinodynamic problems but they often face the problem of regression as they propagate trajectories in already explored space. Heuristic search can be very beneficial in guiding the operation of sampling-based planners in such challenging problems so as to avoid regression and focus the search in the part of the state space that is beneficial to the solution of a problem.”

Advertisements