0%

Path Planning BIT

1. Intro

Basic Method

  • Graph-based: A*, D*
  • Anytime Sampling: RRT, RPM

BIT: combine graph and sampling

  • Use RGG to approximate the searched space

Prove

  • Completeness: can always find a solution from start to goal (if exist)
  • Almost-sure Asymptotic optimality

2. Unknown Term

RGG: random geometry graph

  • A type of mathematical graph
  • Node is randomly distributed in geometric space
A random geometric graph. | Download Scientific Diagram

Lebesgue Measure

  • Assign a numerical value to a subset of euclidean space like line/plane/space
  • Generalize the notion of length/area/volume
  • Use more advanced math tool like calculus and analysis

LPA: lifelong planning A*

  • designed to work in dynamic environment
  • incremental update
  • Maintain two sets of node
  • open: have been generated, not yet expanded
  • closed: have been expanded
  • Each node has two value
  • g: the actual cost
  • rhs: the heuristic estimate

3. Algorithm

Idea:

  • Find a solution from start to goal, form a batch
  • In the next batch, form denser RGG