Skip to main content
Erschienen in: Intelligent Service Robotics 1/2019

09.11.2018 | Original Research Paper

Application of hybrid fast marching method to determine the real-time path for the biped robot

verfasst von: Ravi Kumar Mandava, Mrudul Katla, Pandu R. Vundavilli

Erschienen in: Intelligent Service Robotics | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The research in path planning is very intense in the field of robotics. Researchers around the world are interested in developing various methods to establish the path between a start and goal points in an obstacle-cluttered environment. In the present manuscript, the authors have proposed a solution methodology using fast marching method hybridized with regression search (FMMHRS) to generate an optimal path between the start and goal points in real time. Initially, the path is developed by using a fast marching method (FMM), and later on a regression search algorithm is employed to optimize the path obtained using FMM algorithm. In this work, the efficiency of the developed path planner is tested in simulations. Further, an experimental work is carried out in real-world environment on a two-legged robot to ascertain the path, its length, travelling time and convergence speed of the said approach. It has been observed that the proposed method is found to be superior and efficient when compared with some of the approaches available in the literature.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Chang YC, Yamamoto Y (2009) Path planning of wheeled mobile robot with simultaneous free space locating capability. Intell Serv Robot 2:9–22CrossRef Chang YC, Yamamoto Y (2009) Path planning of wheeled mobile robot with simultaneous free space locating capability. Intell Serv Robot 2:9–22CrossRef
2.
Zurück zum Zitat LaValle S (2011) Motion planning. Robotics Automation Magazine, IEEE 18(1):79–89CrossRef LaValle S (2011) Motion planning. Robotics Automation Magazine, IEEE 18(1):79–89CrossRef
3.
Zurück zum Zitat Kuffner JJ, LaValle S (2000) RRT-connecting efficient approach to single-query path planning. In: IEEE international conference on robotics and automation, vol 2, pp 995–1001 Kuffner JJ, LaValle S (2000) RRT-connecting efficient approach to single-query path planning. In: IEEE international conference on robotics and automation, vol 2, pp 995–1001
4.
Zurück zum Zitat Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4:100–107CrossRef Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4:100–107CrossRef
6.
Zurück zum Zitat Stentz A (1995) The focused D* algorithm for real-time re-planning. In: International joint conference on artificial intelligence Stentz A (1995) The focused D* algorithm for real-time re-planning. In: International joint conference on artificial intelligence
7.
Zurück zum Zitat Kovács B, Szayer G, Tajti F, Burdelis M, Korondi P (2016) A novel potential field method for path planning of mobile robots by adapting animal motion attributes. Robot Auton Syst 82:24–34CrossRef Kovács B, Szayer G, Tajti F, Burdelis M, Korondi P (2016) A novel potential field method for path planning of mobile robots by adapting animal motion attributes. Robot Auton Syst 82:24–34CrossRef
8.
Zurück zum Zitat Melchior P, Orsoni B, Oustaloup A (2001) Weyl fractional potential in path planning. In: European control conference (ECC), pp 1758–1763 Melchior P, Orsoni B, Oustaloup A (2001) Weyl fractional potential in path planning. In: European control conference (ECC), pp 1758–1763
9.
Zurück zum Zitat Oustaloup A, Orsoni B, Melchior P, Linares H (2003) Path planning by fractional differentiation. Robotica 21(1):59–69CrossRef Oustaloup A, Orsoni B, Melchior P, Linares H (2003) Path planning by fractional differentiation. Robotica 21(1):59–69CrossRef
10.
Zurück zum Zitat Melchior P, Metoui B, Najar S, Abdelkrim MN, Oustaloup A (2009) Robust path planning for mobile robot based on fractional attractive force. In: American control conference (ACC), pp 1424–1429 Melchior P, Metoui B, Najar S, Abdelkrim MN, Oustaloup A (2009) Robust path planning for mobile robot based on fractional attractive force. In: American control conference (ACC), pp 1424–1429
11.
Zurück zum Zitat Kelly A (1995) An intelligent predictive control approach to the high-speed cross-country autonomous navigation problem, engineering Kelly A (1995) An intelligent predictive control approach to the high-speed cross-country autonomous navigation problem, engineering
12.
Zurück zum Zitat Thrun S, Bucken A, Burgard W, Fox D, Frohlinghaus T, Hennig D, Hofmann T, Krell M, Schimdt T (1998) Map learning and high-speed navigation in RHINO. In: Kortenkamp D, Bonasso RP, Murphy R (eds) AI-based mobile robots. Case studies of successful robot systems. MIT Press, Cambridge Thrun S, Bucken A, Burgard W, Fox D, Frohlinghaus T, Hennig D, Hofmann T, Krell M, Schimdt T (1998) Map learning and high-speed navigation in RHINO. In: Kortenkamp D, Bonasso RP, Murphy R (eds) AI-based mobile robots. Case studies of successful robot systems. MIT Press, Cambridge
13.
Zurück zum Zitat Brock O, Khatib O (1999) High-speed navigation using the global dynamic window approach. In: IEEE international conference on robotics and automation, vol 1, pp 341–346 Brock O, Khatib O (1999) High-speed navigation using the global dynamic window approach. In: IEEE international conference on robotics and automation, vol 1, pp 341–346
14.
Zurück zum Zitat Philippsen R, Siegwart R (2003) Smooth and efficient obstacle avoidance for a tour guide robot. In: IEEE international conference on robotics and automation, vol 1, pp 446–451 Philippsen R, Siegwart R (2003) Smooth and efficient obstacle avoidance for a tour guide robot. In: IEEE international conference on robotics and automation, vol 1, pp 446–451
15.
Zurück zum Zitat Thrun S, Montemerlo M, Dahlkamp H, Stavens D, Aron A, Diebel J, Fong P, Gale J, Halpenny M, Hoffmann G, Lau K, Oakley C, Palatucci M, Pratt V, Stang P, Strohband S, Dupont C, Jendrossek L-E, Koelen C, Markey C, Rummel C, van Niekerk J, Jensen E, Alessandrini P, Bradski G, Davies B, Ettinger S, Kaehler A, Nefian A, Mahoney P (2006) Stanley: the robot that won the DARPA grand challenge: research articles. J Robot Syst 23(9):661–692 Thrun S, Montemerlo M, Dahlkamp H, Stavens D, Aron A, Diebel J, Fong P, Gale J, Halpenny M, Hoffmann G, Lau K, Oakley C, Palatucci M, Pratt V, Stang P, Strohband S, Dupont C, Jendrossek L-E, Koelen C, Markey C, Rummel C, van Niekerk J, Jensen E, Alessandrini P, Bradski G, Davies B, Ettinger S, Kaehler A, Nefian A, Mahoney P (2006) Stanley: the robot that won the DARPA grand challenge: research articles. J Robot Syst 23(9):661–692
16.
Zurück zum Zitat Howard TM, Kelly A (2007) Optimal rough terrain trajectory generation for wheeled mobile robots. Int J Robot Res 26(2):141–166CrossRef Howard TM, Kelly A (2007) Optimal rough terrain trajectory generation for wheeled mobile robots. Int J Robot Res 26(2):141–166CrossRef
17.
Zurück zum Zitat Urmson C, Ragusa C, Ray D, Anhalt J, Bartz D, Galatali T, Gutierrez E, Johnston J, Clark M, Koon P, Mosher A, Struble J (2006) A robust approach to high-speed navigation for unrehearsed desert terrain. J Field Robot 23:467–508CrossRefMATH Urmson C, Ragusa C, Ray D, Anhalt J, Bartz D, Galatali T, Gutierrez E, Johnston J, Clark M, Koon P, Mosher A, Struble J (2006) A robust approach to high-speed navigation for unrehearsed desert terrain. J Field Robot 23:467–508CrossRefMATH
18.
Zurück zum Zitat Braid D, Broggi A, Schmiedel G (2006) The TerraMax autonomous vehicle. J Field Robot 23(9):693–708CrossRef Braid D, Broggi A, Schmiedel G (2006) The TerraMax autonomous vehicle. J Field Robot 23(9):693–708CrossRef
19.
Zurück zum Zitat Vascak J, Rutrich M (2008) Path planning in dynamic environment using fuzzy cognitive maps. In: 2008 6th international symposium on applied machine intelligence and informatics. IEEE, pp 5–9 Vascak J, Rutrich M (2008) Path planning in dynamic environment using fuzzy cognitive maps. In: 2008 6th international symposium on applied machine intelligence and informatics. IEEE, pp 5–9
20.
Zurück zum Zitat Li G, Tamura Y, Yamashita A, Asama H (2013) Effective improved artificial potential field-based regression search method for autonomous mobile robot path planning. Int J Mechatron Autom 3(3):141–170CrossRef Li G, Tamura Y, Yamashita A, Asama H (2013) Effective improved artificial potential field-based regression search method for autonomous mobile robot path planning. Int J Mechatron Autom 3(3):141–170CrossRef
21.
Zurück zum Zitat Mandava RK, Bondada S, Vundavilli PR (2017) An optimized path planning for the mobile robot using potential field method and PSO algorithm. In: 7th international conference on soft computing and problem solving (socpros-2017), Bhubaneswar, India Mandava RK, Bondada S, Vundavilli PR (2017) An optimized path planning for the mobile robot using potential field method and PSO algorithm. In: 7th international conference on soft computing and problem solving (socpros-2017), Bhubaneswar, India
22.
23.
Zurück zum Zitat Garrido Santiago, Moreno Luis, Blanco Dolores, Jurewicz Piotr (2011) Path planning for mobile robot navigation using voronoi diagram and fast marching. Int J Robot Aut (IJRA) 2(1):42–64 Garrido Santiago, Moreno Luis, Blanco Dolores, Jurewicz Piotr (2011) Path planning for mobile robot navigation using voronoi diagram and fast marching. Int J Robot Aut (IJRA) 2(1):42–64
24.
Zurück zum Zitat Melchior P, Orsoni B, Lavialle O, Poty A, Oustaloup A (2003) Consideration of obstacle danger level in path planning using A* and fast-marching optimization: comparative study. Signal Process 11:2387–2396CrossRefMATH Melchior P, Orsoni B, Lavialle O, Poty A, Oustaloup A (2003) Consideration of obstacle danger level in path planning using A* and fast-marching optimization: comparative study. Signal Process 11:2387–2396CrossRefMATH
25.
Zurück zum Zitat Chiang CH, Chiang PJ (2007) A comparative study of implementing fast marching method and A* search for mobile robot path planning in grid environment: effect of map resolution. In: Proceedings of IEEE advanced robotics and its social impacts, pp 1–6 Chiang CH, Chiang PJ (2007) A comparative study of implementing fast marching method and A* search for mobile robot path planning in grid environment: effect of map resolution. In: Proceedings of IEEE advanced robotics and its social impacts, pp 1–6
26.
Zurück zum Zitat Do QuocHuy, Mita Seiichi, Yoneda Keisuke (2013) A practical and optimal path planning for autonomous parking using fast marching algorithm and support vector machine. IEICE Trans Inf Syst 96(12):2795–2804CrossRef Do QuocHuy, Mita Seiichi, Yoneda Keisuke (2013) A practical and optimal path planning for autonomous parking using fast marching algorithm and support vector machine. IEICE Trans Inf Syst 96(12):2795–2804CrossRef
27.
Zurück zum Zitat Do QH, Mita S, Yoneda K (2014) Narrow passage path planning using fast marching method and support vector machine. In: 2014 IEEE intelligent vehicles symposium (IV) Do QH, Mita S, Yoneda K (2014) Narrow passage path planning using fast marching method and support vector machine. In: 2014 IEEE intelligent vehicles symposium (IV)
28.
Zurück zum Zitat Liu Y, Song R, Bucknall R (2015) A practical path planning and navigation algorithm for an unmanned surface vehicle using the fast marching algorithm. In: OCEANS 2015—Genova, Italy, pp 1–7 Liu Y, Song R, Bucknall R (2015) A practical path planning and navigation algorithm for an unmanned surface vehicle using the fast marching algorithm. In: OCEANS 2015—Genova, Italy, pp 1–7
29.
30.
Zurück zum Zitat Gomez JV (2012) Advanced applications of the fast marching square planning method. Master’s thesis, Carlos III University Gomez JV (2012) Advanced applications of the fast marching square planning method. Master’s thesis, Carlos III University
31.
Zurück zum Zitat Forcadel N, Le Guyader C, Gout C (2008) Generalized fast marching method: applications to image segmentation. Numer Algorithms 48(1–3):189–211MathSciNetCrossRefMATH Forcadel N, Le Guyader C, Gout C (2008) Generalized fast marching method: applications to image segmentation. Numer Algorithms 48(1–3):189–211MathSciNetCrossRefMATH
32.
Zurück zum Zitat Basu S, Racoceanu D (2014) Reconstructing neuronal morphology from microscopy stacks using fast marching. In: IEEE international conference on image processing, pp 3597–3601 Basu S, Racoceanu D (2014) Reconstructing neuronal morphology from microscopy stacks using fast marching. In: IEEE international conference on image processing, pp 3597–3601
33.
Zurück zum Zitat Qu X, Liu S, Wang F (2014) A new ray tracing technique for cross hole radar travel time tomography based on multistencils fast marching method and the steepest descend method. In: 15th international conference on ground penetrating radar, pp 503–508 Qu X, Liu S, Wang F (2014) A new ray tracing technique for cross hole radar travel time tomography based on multistencils fast marching method and the steepest descend method. In: 15th international conference on ground penetrating radar, pp 503–508
34.
Zurück zum Zitat Zhang X, Bording R (2011) Fast marching method seismic travel times with reconfigurable field programmable gate arrays. Can J Explor Geophys 36(1):60–68 Zhang X, Bording R (2011) Fast marching method seismic travel times with reconfigurable field programmable gate arrays. Can J Explor Geophys 36(1):60–68
35.
Zurück zum Zitat Osher S, Sethian JA (1988) Fronts propagating with curvature dependent speed: algorithms based on Hamilton–Jacobi formulations. J Comput Phys 79(1):12–49MathSciNetCrossRefMATH Osher S, Sethian JA (1988) Fronts propagating with curvature dependent speed: algorithms based on Hamilton–Jacobi formulations. J Comput Phys 79(1):12–49MathSciNetCrossRefMATH
36.
Zurück zum Zitat Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, pp 1942–1948 Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, pp 1942–1948
37.
Zurück zum Zitat Mandava RK, Vundavilli PR (2018) Whole body motion generation of 18-DOF biped robot on flat surface during SSP and DSP. Int J Model Identif Control 29(3):266–277CrossRef Mandava RK, Vundavilli PR (2018) Whole body motion generation of 18-DOF biped robot on flat surface during SSP and DSP. Int J Model Identif Control 29(3):266–277CrossRef
38.
Zurück zum Zitat Kuffner Jr. JJ, Nishiwaki K, Kagami S, Inaba M, Inoue H (2001) Footstep planning among obstacles for biped robots. In: Proceedings of 2001 IEEE RSJ international conference on intelligent robots and systems, Maui, Hawaii, USA, Oct 29–NOV. 03, pp 500–505 Kuffner Jr. JJ, Nishiwaki K, Kagami S, Inaba M, Inoue H (2001) Footstep planning among obstacles for biped robots. In: Proceedings of 2001 IEEE RSJ international conference on intelligent robots and systems, Maui, Hawaii, USA, Oct 29–NOV. 03, pp 500–505
39.
Zurück zum Zitat Hildebrandt AC, Klischat M, Wahrmann D, Wittmann R, Sygulla F, Seiwald P, Rixen D, Buschmann T (2017) Real-time path planning in unknown environments for bipedal robots. IEEE Robot Autom Lett 2(4):1856–1863CrossRef Hildebrandt AC, Klischat M, Wahrmann D, Wittmann R, Sygulla F, Seiwald P, Rixen D, Buschmann T (2017) Real-time path planning in unknown environments for bipedal robots. IEEE Robot Autom Lett 2(4):1856–1863CrossRef
Metadaten
Titel
Application of hybrid fast marching method to determine the real-time path for the biped robot
verfasst von
Ravi Kumar Mandava
Mrudul Katla
Pandu R. Vundavilli
Publikationsdatum
09.11.2018
Verlag
Springer Berlin Heidelberg
Erschienen in
Intelligent Service Robotics / Ausgabe 1/2019
Print ISSN: 1861-2776
Elektronische ISSN: 1861-2784
DOI
https://doi.org/10.1007/s11370-018-0268-7

Weitere Artikel der Ausgabe 1/2019

Intelligent Service Robotics 1/2019 Zur Ausgabe

Neuer Inhalt