We present a novel trajectory computation algorithm to smooth piecewise linear collision-free trajectories computed by sample-based motion planners. Our approach uses cubic B-splines to generate trajectories that are C2 almost everywhere, except on a few isolated points. The algorithm performs local spline refinement to compute smooth, collision-free trajectories and it works well even in environments with narrow passages. We also present a fast and reliable algorithm for collision checking between a robot and the environment along the B-spline trajectories. We highlight the performance of our algorithm on complex benchmarks, including path computation for rigid and articulated models in cluttered environments.
BarrAHCurrinBGabrielSHughesJF (1992) Smooth interpolation of orientations with angular velocity constraints using quaternions. In: Proceedings of international conference on computer graphics and interactive techniques, pp. 313–320.
2.
BarskyBADeRoseTD (1989) Geometric continuity of parametric curves: Three equivalent characterizations. IEEE Computer Graphics and Applications9(6): 60–68.
3.
BrockOKhatibO (2002) Elastic strips: A framework for motion generation in human environments. International Journal of Robotics Research18(6): 1031–1052.
4.
ChangH (1995) Motion planning in virtual prototyping: Practical considerations. In: Proceedings of IEEE international symposium on assembly and task planning, pp. 427–428.
5.
DeRoseTDBarskyBA (1988) Geometric continuity, shape parameters, and geometric constructions for Catmull-Rom splines. ACM Transactions on Graphics, 1–41.
6.
FangYHsiehCKimMChangJWooT (1998) Real time motion fairing with unit quaternions. Computer-Aided Design30(3): 191–198.
7.
FarinG (1993) Curves and Surfaces for Computer Aided Geometric Design (3rd ed.): A Practical Guide. Academic Press Professional, Inc.: San Diego, CA, USA.
8.
FroissartCMechlerP (1993) On-line polynomial path planning in Cartesian space for robot manipulators. Robotica11(03): 245–251.
9.
GeraertsROvermarsMH (2007) Creating high-quality paths for motion planning. International Journal of Robotics Research26(8) 845–863.
10.
GovindarajuNKKnottDJainNKabulITamstorfRGayleRLinMCManochaD (2005) Interactive collision detection between deformable models using chromatic decomposition. ACM Transactions on Graphics24: 991–999.
11.
HauserKNg-Thow-HingV (2010) Fast smoothing of manipulator trajectories using optimal bounded-acceleration shortcuts. In: Proceedings of international conference on robotics and automation.
12.
JailletLSimeonT (2008) Path deformation roadmaps: Compact graphs with useful cycles for motion planning. International Journal of Robotics Research27(11–12): 1175–1188.
13.
KallmannMAubelAAbaciTThalmannD (2003) Planning collision-free reaching motions for interactive object manipulation and grasping. Computer Graphics Forum22(3): 313–322.
14.
KaneharaMKagamiSKuffnerJThompsonSMizoguhiH (2007) Path shortening and smoothing of grid-based path planning with consideration of obstacles. In: Proceedings of IEEE international conference on systems, man and cybernetics, pp. 991–996.
15.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research30(7): 846–894.
16.
KavrakiLSvestkaPLatombeJCOvermarsM (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation12(4): 566–580.
17.
KimM-JKimM-SShinSY (1995) A general construction scheme for unit quaternion curves with simple high order derivatives. In: Proceedings of international conference on computer graphics and interactive techniques, pp. 369–376.
18.
KrebsHIHoganNAisenMLVolpeBT (1998) Robot-aided neurorehabilitation. IEEE Transactions on Rehabilitation Engineering6(1): 75–87.
19.
KuffnerJLaValleS (2000) RRT-connect: An efficient approach to single-query path planning. In: Proceedings of international conference on robotics and automation.
20.
LaValleSM (2006) Planning Algorithms. Cambridge University Press.
21.
LeeS-HKimJParkFKimMBobrowJE (2005) Newton-type algorithms for dynamics-based robot movement optimization. IEEE Transactions on Robotics21(4): 657–667.
22.
LengagneSKheddarAYoshidaE (2011) Generation of optimal dynamic multi-contact motions: Application to humanoid robots. IEEE Transactions on Robotics. Submitted.
23.
MarbleJDBekrisKE (2011) Asymptotically near-optimal is good enough for motion planning. In: Proceedings of international symposium on robotics research.
24.
MurrayRLiZSastryS (1994) A Mathematical Introduction to Robotic Manipulation. CRC Press.
25.
NajfeldIHavelTF (1995) Derivatives of the matrix exponential and their computation. Advances in Applied Mathematics16: 321–375.
26.
NielsonGM (2004) -quaternion splines for the smooth interpolation of orientations. IEEE Transactions on Visualization and Computer Graphics10(2): 224–229.
27.
NieuwenhuisenDOvermarsMH (2004) Useful cycles in probabilistic roadmap graphs . In: Proceedings of international conference on robotics and automation, pp. 446–452.
28.
PanJChittaSManochaD (2012) FCL: A general purpose library for collision and proximity queries. In: Proceedings of international conference on robotics and automation, to appear.
29.
PanJZhangLManochaD (2010) Retraction-based RRT planner for articulated models. In: Proceedings of international conference on robotics and automation, pp. 2529–2536.
30.
PanJZhangLManochaD (2011) Collision-free and curvature-continuous path smoothing in cluttered environments. In: Robotics: Science and Systems.
31.
PettreJSimeonTLaumondJ (2002) Planning human walk in virtual environments. In: Proceedings of international conference on intelligent robots and systems, vol. 3, pp. 3048–3053.
RatliffNZuckerMBagnellJADSrinivasaS (2009) CHOMP: Gradient optimization techniques for efficient motion planning. In: Proceedings of international conference on robotics and automation, pp. 489–494.
34.
RedonSKimYJLinMCManochaD (2004) Fast continuous collision detection for articulated models. In: Proceedings of ACM symposium on solid modeling and applications, pp. 145–156.
35.
ShoemakeK (1985) Animating rotation with quaternion curves. In: Proceedings of international conference on computer graphics and interactive techniques, pp. 245–254.
36.
TangMKimYManochaD (2011) CCQ: Efficient local planning using connection collision query. In: Algorithmic Foundations of Robotics IX, vol. 68 of Springer Tracts in Advanced Robotics, pp. 229–247.
37.
ToussaintMGiengerMGoerickC (2007) Optimization of sequential attractor-based movement for compact behavior generation. In: Proceedings of international conference on humanoid robots, pp. 122–129.
38.
YamaneKKuffnerJJHodginsJK (2004) Synthesizing animations of human manipulation tasks. ACM Transactions on Graphics23(3): 532–539.
39.
YangKSukkariehS (2010) An analytical continuous-curvature path-smoothing algorithm. IEEE Transactions on Robotics26(3): 561–568.
40.
ZhangLHuangXKimYJManochaD (2008) D-Plan: Efficient collision-free path computation for part removal and disassembly. Journal of Computer-Aided Design and Applications5(6): 774–786.
41.
ZhangXLeeMKimYJ (2006) Interactive continuous collision detection for non-convex polyhedra. The Visual Computer22(9): 749–760.
42.
ZhangXRedonSLeeMKimYJ (2007) Continuous collision detection for articulated models using Taylor models and temporal culling. ACM Transactions on Graphics26(3): 15:1–15:10.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
