Roadmaps

Similar data structure to roadmaps designed by humans where you start by planning your path along highways and then work out the details.

Definition- Roadmap: A union of one-dimensional curves is a roadmapp RM iff for all $q_{start}$ and $q_{goal}$ in $Q_{free}$ that can be connected by a path, the following properties hold.

1. Accessibility: there exists a path from $q_{start}\in Q_{free}$ to some $q_{start}^{{}^{\prime }}\in RM$
2. Departability: there exists a path from some $q_{goal}^{{}^{\prime }}\in RM$ to $q_{goal}\in Q_{free}$
3. Connectivity: there exists a path in $RM$ between $q_{start}^{{}^{\prime }}$ and $q_{goal}^{{}^{\prime }}$.

5 types of roadmaps:

• Visibility maps
• deformation retracts
• retract-like structures
• piecewise retracts
• silhouettes