Abstract In robot motion planning, many algorithms have been proposed that create a roadmap from which a path for a moving object can be extracted. These algorithms generally do not give guarantees on the quality of the roadmap, i.e. they do not promise that a path will always be found in the roadmap if one exists in the world. Furthermore, such roadmaps often become very large which can cause memory problems and high query times. We present a new efficient algorithm that creates small roadmaps for two- and three-dimensional problems. The algorithm ensures that a path is always found (if one exists) at a given resolution. These claims are verified on a broad range of environments. The results also give insight in the structure of covering roadmaps. Reference Roland Geraerts and Mark Overmars. Creating Small Roadmaps for Solving Motion Planning Problems. In IEEE International Conference on Methods and Models in Automation and Robotics (MMAR'05), 2005, pp. 531-536. Full text: [pdf, ps.gz] Presentation: [ppt] Small roadmap for a large 3D environment A more elaborate version of this study can be found in Chapter 6 of my Ph.D. thesis. Experimental results We created small roadmaps for the following 2D environments. The left column shows the environments and their roadmaps. The green and red nodes are the guards that see the whole environment. The blue nodes are the connectors. Click on a picture to see the corresponding result in VRML. (You need to have a VRML-client to view them.) Name: planar1 Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 0.04 8 7 64 0 2.17 16 15 153 0 0.02 13 12 112 0 Name: prm1 Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 0.16 39 38 560 0 10.802 53 50 952 0 0.24 185 184 1380 0 Name: grid Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 0.33 13 12 88 2 20.49 31 30 381 14 0.74 158 157 638 4 Name: rotated grid Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 6.78 249 248 388 1 >3600.00 n.a. n.a. n.a. n.a. 16.31 5889 5887 2328 20 We created small graphs for the following 3D environments. Name: house Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 18.90 36 35 280 11 >3600.00 n.a. n.a. n.a. n.a. 4.4 977 976 3489 6 Name: village Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 556.44 176 142 1268 0 >3600.00 n.a n.a. n.a. n.a. >3600.00 n.a n.a n.a n.a Name: manipulator1 Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 0.98 48 47 100 15 >3600.00 n.a. n.a. n.a. n.a. 2.99 362 360 221 12 Name: manipulator2 Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 10.81 313 306 380 0 >3600.00 n.a. n.a. n.a. n.a. 86.24 11095 11091 2306 41 Name: corridor Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 0.32 17 16 157 0 1.85 18 15 218 0 0.07 54 53 368 0 Name: rooms Statistic Reachability Visibility PRM   construction time (s) number of nodes number of edges length graph query time (ms) 0.08 5 4 53 0 0.05 7 4 83 0 0.02 14 13 156 0