Paper Titles

The Spectral Element Method for the Steklov Eigenvalue Problem
p.631

Linear Matrix Inequality and its Application in Control Theory
p.636

Study of Fault Arc Protection Based on UV Pulse Method in High Voltage Switchgear
p.641

Intelligent Aquaculture Monitoring System Based on Fieldbus
p.646

A Survey on Randomized Sampling-Based Path Optimization Methods
p.652

Three-Dimensinal Structure Modeling of Lishui Depression, East China Sea Basin
p.663

A Review on the Bin Packing Capacitated Vehicle Routing Problem
p.668

A Novel Model for Multi-Parametric Load Balance in Grid Computing
p.674

Research on Piano Music Signal Recognition Based on Short-Time Fourier Analysis
p.680

HomeAdvanced Materials ResearchAdvanced Materials Research Vol. 853A Survey on Randomized Sampling-Based Path...

A Survey on Randomized Sampling-Based Path Optimization Methods

Article Preview

Abstract:

Randomized sampling-based motion planners could efficiently generate collision-free motion paths. However, these paths have some quality problems (with respect to quality measures, such as path length, clearance and smoothness), especially in high dimensional configuration spaces. Thus, researchers studied some path optimization methods to improve path quality and to make paths suitable for practical applications. This paper reviews some of the most influential path optimization methods and gives an overall perspective on the most widely used ideas in the field.

You might also be interested in these eBooks

Materials Science, Machinery and Energy Engineering

Info:

Periodical:

Advanced Materials Research (Volume 853)

Pages:

652-660

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.853.652

Citation:

Cite this paper

Online since:

December 2013

Authors:

Fu Yu Yan*, Fan Wu, Fei Peng, Zhi Jie Zhu

Keywords:

Path Optimization, Path Quality, Sampling-Based Motion Planning

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2014 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

* - Corresponding Author

[1] T. Berglund, U. Erikson, H. Jonsson, K. Mrozek, and I. Soderkvist: Int. Conf. on Computational Intelligence for Modeling Control and Automation (2001).

[2] F. Lamireaux, D. Bonnafous, and C. V. Geem: Workshop Control Problems in Robotics and Automation (2002), pp.1-18.

[3] F. Lamiraux and J. -P. Laumond: Smooth motion planning for car-like vehicles (IEEE Trans. on Robotics and Automation, 2001).

DOI: 10.1109/70.954762

[4] M. Yamamoto, M. Iwamura, and A. Mohri: IEEE Int. Conf. on Robotics and Automation (1999), pp.2958-2963.

[5] G. Song and N. M. Amato: IEEE Int. Conf. on Intelligent Robots and Systems (2001), pp.37-42.

[6] B. Baginski: Int. Workshop on Robotics in the Alpe-Adria-Danube Region (1997), pp.247-252.

[7] B. Baginski: Motion planning for manipulators with many degrees of freedom - the BB-method (Ph.D. dissertation, Technische Universität Münchena 1998).

[8] R. Bohlin: Motion planning for industrial robots (Ph.D. dissertation, Goteborg Univ., Sweden 1999).

[9] D. Hsu, J. -C. Latombe, and S. Sorkin: IEEE Int. Symp. on Assembly and Task (1999), pp.280-285.

[10] C. V. Geem, T. SimCon, and J. -P. Laumond: IEEE Int. Conf. on Robotics and Automation (1999), pp.1770-1775.

[11] D. Nieuwenhuisen and M. H. Overmars: Motion planning for camera movements (Utrecht Univ., Technical Report 2003-004, 2003).

[12] G. Song and N. Amato: Using motion planning to study protein folding pathways (Journal of Computational Biology).

[13] J. J. Kuffner, K. Nishiwaki, S. Kagami, M. Inaba, and H. Inoue: IEEE Int. Conf. on Robotics and Automation (2001), pp.692-698.

[14] H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun, in Principles of robot motion: Theory, algorithms, and implementations, 1st ed,. Cambridge, MA: MIT Press, (2005).

DOI: 10.1017/s0269888907218016

[15] J. -C. Latombe, in Robot motion planning. Boston, MA: Kluwer Academic Publishers, (1991).

[16] S. M. LaValle, in Planning Algorithms. Cambridge, U.K.: Cambridge Univ. Press, (2006).

[17] S. R. Lindemann and S. M. LaValle: Proc. 11th Int. Symp. of Robotics Research (2003).

[18] J. Canny and J. Reif: IEEE Symp. on Foundations of Computer Science (1987), pp.49-60.

[19] T. Asano, D. Kirkpatrick, and C. Yap: Proc. 12th ACM Symp. on Compution Geometry (1996), pp.252-263.

[20] J. Reif and H. Wang: IEEE Workshop on Foundations of Robotics (1998), pp.49-57.

[21] J. S. B. Mitchell, in Handbook of Discrete and Computational Geometry. Boca Raton, FL: CRC, (2004).

[22] V. Boor, A. Kamphuis, C. Gem, E. Schmitzberger, and J. Bouchet: Formalisation of path quality (Delivery MOLOG Project, 2000).

[23] L. Kavraki and J. -C. Latombe: IEEE Int. Conf. on Robotics and Automation (1994), pp.2138-2139.

[24] L. Kavraki, P. Svestka, J. -C. Latombe, and M. H. Overmars: Probabilistic roadmaps for path planning in high-dimensional configuration spaces (IEEE Trans. on Robotics and Automation, 1996).

DOI: 10.1109/70.508439

[25] S. M. LaValle: Rapidly-exploring random trees: A new tool for path planning (Iowa State Univ., Technical Report TR98-11, 1998).

[26] J. J. Kuffner and S. M. LaValle: IEEE Int. Conf. on Robotics and Automation (2000), pp.995-1001.

[27] E. W. Dijkstra: A note on two problems in connexion with graphs (Numerische Mathematik, 1959).

[28] J. Orlin: Network Flows (New Jersey: Prentice Hall, Upper Saddle River, 1993).

[29] A. Papadatos: Research on motion planning of autonomous mobile robot (M.S. thesis, Naval Postgraduate School, Monterrey, California, USA, 1996).

[30] J. Kim, R. A. Pearce, and N. M. Amato: IEEE Int. Conf. on Robotics and Automation (2003), pp.2424-2429.

[31] R. Geraerts and M. H. Overmars: Workshop on the Algorithmic Founda- tions of Robotics (2002), pp.43-57.

[32] C. Nissoux, T. Simeon, and J. -P. Laumond: IEEE Int. Conf. on Intelligent Robots and Systems (1999), pp.1316-1321.

[33] R. Geraerts and M. H. Overmars: Conf. on Intelligent Autonomous Systems (2004), pp.600-609.

[34] R. Geraerts and M. H. Overmars: IEEE Int. Conf. on Methods and Models in Automation and Robotics (2005), pp.531-536.

[35] D. Nieuwenhuisen and M. H. Overmars: IEEE Int. Conf. on Robotics and Automation (2004), pp.446-452.

[36] R. Geraens and M. H. Overmars: IEEE Int. Conf. on Robotics and Automation (2004), pp.2386-2392.

[37] R. Geraerts and M. H. Overmars: Creating high-quality paths for motion planning (Int. Journal of Robotics Research, 2007).

[38] L. E. Kavrak and J. -C. Latombe, in Probabilistic roadmaps for robot path planning, Practical Motion Planning in Robotics: Current Approaches and Future Directions, edtied by K. Gupta and A. del Pobil, John Wiley, (1998).

[39] P. Isto: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (2002), pp.2323-2328.

[40] J. de Smith: Distance and path: the development, interpretation and application of distance measurement in mapping and modeling (Ph.D. dissertation, Univ. College, Univ. of London, London, U.K., 2003).

[41] L. Feng and Q. Jia: Improved algorithm of RRT path planning based on comparison optimization , (Computer Engineering and Applications, 2011).

[42] S. A. Wilmarth, N. M. Amato, and P. F. Stiller: IEEE Int. Conf. on Robotics and Automation (1999), pp.1024-1031.

[43] E. Aurenhammer: Voronoi diagrams: A survey of a fundamental geometric data structure (ACM Computer Surver, 1991).

DOI: 10.1145/116873.116880

[44] S. A. Wilmarth, N. M. Amato, and P. F. Stiller: Proc. ACM Symp. on Computational Geometry (1999), pp.173-180.

[45] J. -M. Lien, S. L. Thomas, and N. M. Amato: IEEE Int. Conf. on Robotics and Automation (2003), pp.4439-4444.

[46] R. Geraerts and M. H. Overmars: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (2005), pp.679-684.

[47] E. Schmitzberger, J. L. Bouchet, M. Dufaut, D. Wolf, and R. Husson: IEEE/RSJ Int. Conf. on lntelligent Robots and Systems (2002), pp.2317-2322.

DOI: 10.1109/irds.2002.1041613

[48] G. Song, S. Miller, and N. M. Amato: IEEE Int. Conf. on Robotics and Automation (2001), pp.1500-1505.

[49] D. Nieuwenhuisen, A. Kamphuis, M. Mooijekind, and M. H. Overmars: Automatic construction of high quality roadmaps for path planning (Utrecht Univ., Technical Report UU-CS-2004-068, 2004).

[50] R. Wein, J. van den Berg, and D. Halperin: The visibility-voronoi complex and its applications (Computational Geometry: Theory and Applications, 2007).

DOI: 10.1016/j.comgeo.2005.11.007

[51] R. Geraerts and M. H. Overmars: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (2006), pp.4355-4361.

[52] S. Karaman and E. Frazzoli: submitted to Int. Journal of Robotic Research.

[53] D. Ferguson and A. Stentz: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (2006), pp.5369-5385.

[54] B. Raveh, A. Enosh, and D. Halperin: A little more, a lot better: Improving path quality by a path-merging algorithm (IEEE Trans. on Robotics, 2011).

DOI: 10.1109/tro.2010.2098622

[55] A. Kamphuis and M. H. Overmars: Eurographics/ACM SIGGRAPH Symp. on Computer Animation (2004), pp.19-28.

[56] R. Wein, J. Berg, and D. Halperin: Int. Workshop on the Algorithmic Foundations of Robotics (2006).

[57] J. Pettre, P. de H. Ciechomski, J. Maim, B. Yersin, J. -P. Laumond, and D. Thalmann: Real-time navigating crowds: Scalable simulation and rendering (Computer Animation and Virtual Worlds, 2006).

DOI: 10.1002/cav.147

[58] R. Geraerts and M. H. Overmars: The corridor map method: A general framework for real-time high-quality path planning (Computer Animation and Virtual Worlds, 2007).

DOI: 10.1002/cav.166

[59] R. Geraerts: IEEE Int. Conf. on Robotics and Automation (2010), p.1997-(2004).

[60] I. Karamouzas, R. Geraerts, and M. H. Overmars: The 4th Int. Conf. on the Foundations of Digital Games (2009), p.113–120.