3D Mapping example Cell decomposition example Motion Planning Skeletonization:Voronoi diagram plan in configuratio space define y th ot's DOF Problem:doesn'ale well to Configuration space planning Skeletonization:Probabilistic Roadmap Basic problem:states!Convert to finite state space.3D Mapping example Chapter 25 13 Motion Planning Idea: plan in configuration space defined by the robot’s DOFs conf-3 conf-1 conf-2 conf-3 conf-2 conf-1 w w elb shou Solution is a point trajectory in free C-space Chapter 25 14 Configuration space planning Basic problem: ∞d states! Convert to finite state space. Cell decomposition: divide up space into simple cells, each of which can be traversed “easily” (e.g., convex) Skeletonization: identify finite number of easily connected points/lines that form a graph such that any two points are connected by a path on the graph Chapter 25 15 Cell decomposition example start goal start goal Problem: may be no path in pure freespace cells Solution: recursive decomposition of mixed (free+obstacle) cells Chapter 25 16 Skeletonization: Voronoi diagram Voronoi diagram: locus of points equidistant from obstacles Problem: doesn’t scale well to higher dimensions Chapter 25 17 Skeletonization: Probabilistic Roadmap A probabilistic roadmap is generated by generating random points in C-space and keeping those in freespace; create graph by joining pairs by straight lines Problem: need to generate enough points to ensure that every start/goal pair is connected through the graph Chapter 25 18