Many problems in robot motion planning involve collision testing a set of local paths. In this paper we propose a novel solution to this problem by exploiting the structure of paths and the outcome of previous collision tests. Our approach circumvents expensive collision tests on a given path by detecting that the entire geometry of the path has effectively already been tested on a combination of other paths. We define a homotopy-like equivalence relation among local paths to detect this condition, and we provide algorithms that (1) classify paths based on equivalence, and (2) circumvent collision testing on up to 90% of them. We then prove both correctness and completeness of these algorithms and provide experimental results demonstrating a performance increase up to 300% in the rate of path tests. Additionally, we apply our equivalence relation to the navigation problem in a planning algorithm that takes advantage of information gained from equivalence relationships among collision-free paths. Finally, we explore applications of path equivalence to several other mechanisms, including kinematic chains and medical steerable needles.
AllenTUnderwoodJSchedingS (2007) A path planning system for autonomous ground vehicles operating in unstructured dynamic environments. In: Proceedings of the Australasian Conference on Robotics and Automation.
2.
AlterovitzRBranickyMGoldbergK (2008) Motion planning under uncertainty for image-guided medical needle steering. International Journal of Robotics Research27: 1361–1374.
3.
BarraquandJLatombeJC (1993) Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles. Algorithmica10: 121–155.
4.
BhattacharyaSKumarVLikhachevM (2010) Search-based path planning with homotopy class constraints. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence.
5.
BlumH (1967) A transformation for extracting new descriptors of shape. In: Whaters-DunnW (ed.) Proceedings of the Symposium on Models for the Perception of Speech and Visual FormCambridge, MA: MIT Press, 362–380.
6.
BorensteinJKorenY (1991) The vector field histogram—fast obstacle avoidance for mobile robots. IEEE Transactions on Robotics and Automation7: 278–288.
7.
BrockOKhatibO (2002) Elastic strips: A framework for motion generation in human environments. International Journal of Robotics Research21: 1031–1052.
8.
BuhmannJBurgardWCremersABFoxDHofmannTSchneiderFE. (1995) The mobile robot RHINO. AI Magazine16: 31–38.
9.
ChosetHBurdickJ (1995) Sensor based planning, part I: The generalized Voronoi graph. In: Proceedings of the International Conference on Robotics and Automation, pp. 1649–1655.
10.
ChosetHRizziAA (2005) Topology in motion planning. In: Proceedings of the Eleventh International Symposium on Robotics Research, pp. 90–99.
GardiolNHKaelblingLP (2007) Action-space partitioning for planning. In: Proceedings of the National Conference on Artificial Intelligence.
13.
GreenCKellyA (2007) Toward optimal sampling in the space of paths. In: Proceedings of the Thirteenth International Symposium of Robotics Research.
14.
HenriksonJ (1999) Completeness and total boundedness of the Hausdorff metric. MIT Undergraduate Journal of Mathematics1.
15.
JailletLSimeonT (2008) Path deformation roadmaps: Compact graphs with useful cycles for motion planning. International Journal of Robotics Research27: 1175–1188.
16.
KavrakiLSvestkaPLatombeJCOvermarsM (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. In: Proceedings of the International Conference on Robotics and Automation, pp. 566–580.
17.
KellyAStentzAAmidiOBodeMWBradleyDDiaz-CalderonA. (2006) Toward reliable off road autonomous vehicles operating in challenging environments. International Journal of Robotics Research25: 449–483.
18.
KhatibO (1985) Real-time obstacle avoidance for manipulators and mobile robots. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 500–505.
19.
KnepperRAMasonMT (2008) Empirical sampling of path sets for local area motion planning. In: Proceedings of the International Symposium on Experimental Robotics.
20.
KnepperRAMasonMT (2009) Path diversity is only part of the problem. In: Proceedings on the International Conference on Robotics and Automation.
21.
KnepperRASrinivasaSSMasonMT (2010a) Curvature bounds on the weighted Voronoi diagram of two proximal paths with shape constraints. Technical Report CMU-RI-TR-10-25. Robotics Institute, Carnegie Mellon University.
22.
KnepperRASrinivasaSSMasonMT (2010b) Hierarchical planning architectures for mobile manipulation tasks in indoor environments. In: Proceedings of the International Conference on Robotics and Automation, pp. 1985–1990.
23.
LaumondJP (1986) Feasible trajectories for mobile robots with kinematic and environment constraints. In: Proceedings of the International Conference on Intelligent Autonomous Systems, pp. 346–354.
24.
LaValleSMBranickyMSLindemannSR (2004) On the relationship between classical grid search and probabilistic roadmaps. International Journal of Robotics Research23: 673–692.
25.
LaValleSMKuffnerJJ (2001) Randomized kinodynamic planning. International Journal of Robotics Research20: 378–400.
Marder-EppsteinEBergerEFooteTGerkeyBKonoligeK (2010) The office marathon: Robust navigation in an indoor office environment. In: Proceedings of the International Conference on Robotics and Automation, pp. 300–307.
28.
MinhasDSEnghJAFenskeMMRiviereCN (2007) Modeling of needle steering via duty-cycled spinning. In: Proceedings of the Conference of the IEEE Engineering in Medicine and Biology Society, pp. 2756–2759.
29.
MunkresJR (2000) Topology. Upper Saddle River, NJ: Prentice Hall.
30.
NiederreiterH (1992) Random Number Generation and Quasi-Monte-Carlo Methods. Philadelphia: Society for Industrial Mathematics.
31.
ReedsJASheppLA (1990) Optimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics145: 367–393.
32.
ReifJWangH (1998) The complexity of the two dimensional curvature-constrained shortest-path problem. In: Third International Workshop on Algorithmic Foundations of Robotics, pp. 49–57.
33.
SamplP (2001) Medial axis construction in three dimensions and its application to mesh generation. Engineering with Computers17: 234–248.
34.
SánchezGLatombeJC (2002) On delaying collision checking in PRM planning: Application to multi-robot coordination. International Journal of Robotics Research21: 5–26.
35.
SchmitzbergerEBouchetJDufautMWolfDHussonR (2002) Capture of homotopy classes with probabilistic road map. In: Proceedings of the International Conference on Intelligent Robots and Systems, pp. 2317–2322.
36.
SchwarzerFSahaMLatombeJ (2004) Exact collision checking of robot paths. In: Proceedings of the Workshop on the Algorithmic Foundations of Robotics, pp. 25–41.
37.
SimmonsR (1996) The curvature-velocity method for local obstacle avoidance. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3375–3382.
38.
SunKLumelskyVJ (1991) Motion planning for three-link robot arm manipulators operating in an unknown three-dimensional environment. In: Proceedings of the Thirtieth IEEE Conference on Decision and Control, pp. 1019–1026.
39.
ThorpeCE (1984) Path relaxation: Path planning for a mobile robot. In: Proceedings of the National Conference on Artificial Intelligence, pp. 318–321.
40.
van den BergJPatilSAlterovitzRAbbeelPGoldbergK (2010) LQG-based planning, sensing, and control of steerable needles. In: Proceedings of the Ninth International Workshop on the Algorithmic Foundations of Robotics, pp. 373–389.
41.
VendittelliMLaumondJPNissouxC (1999) Obstacle distance for car-like robots. IEEE Transactions on Robotics and Automation15: 678–691.
42.
WebsterRJIIIKimJSCowanNJChirikjianGSOkamuraAM (2006) Nonholonomic modeling of needle steering. International Journal of Robotics Research25: 509–525.
43.
YapCK (1987) An O(nlogn) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete & Computational Geometry2: 365–393.
44.
YuYGuptaK (2000) An information theoretic approach to view point planning for motion planning of eye-in-hand systems. In: Proceedings of the International Symposium on Robotics, pp. 306–311.
