Skip to main content

2016 | OriginalPaper | Buchkapitel

On Heading Change Measurement: Improvements for Any-Angle Path-Planning

verfasst von : Pablo Muñoz, María D. R-Moreno

Erschienen in: Novel Applications of Intelligent Systems

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

Finding the most efficient and safe path between locations is a ubiquitous problem that occurs in smart phone GPS applications, mobile robotics and even video games. Mobile robots in particular must often operate in any type of terrain. The problem of finding the shortest path on a discretized, continuous terrain has been widely studied, and many applications have been fielded, including planetary exploration missions (i.e. the MER rovers). In this chapter we review some of the most well known path-planning algorithms and we propose a new parameter that can help us to compare them under a different measure: the heading changes and to perform some improvements in any-angle path-planning algorithms. First, we define a heuristic function to guide the process towards the objective, improving the computational cost of the search. Results show that algorithms using this heuristic get better runtime and memory usage than the former ones, with a slightly degradation of other parameters such as path length. And second, we modify an any-angle path-planning algorithm to consider heading changes during the search in order to minimize them. Experiments show that this algorithm obtains smoother paths than the other algorithms tested.

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!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Datasets and full resolution bar plots could be obtained in: http://​ogate.​atspace.​eu/​novelappai/​dataset.​html.
 
Literatur
1.
Zurück zum Zitat S. Russell, P. Norvig, Artificial Intelligence: a Modern Approach (Morgan Kaufmann Publishers, 3 edn., 2009) S. Russell, P. Norvig, Artificial Intelligence: a Modern Approach (Morgan Kaufmann Publishers, 3 edn., 2009)
2.
Zurück zum Zitat D. Higgins, AI Game Programming Wisdom, chapter 3.3 (Charles River Media, 2002) D. Higgins, AI Game Programming Wisdom, chapter 3.3 (Charles River Media, 2002)
4.
Zurück zum Zitat P. Hart, N. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths. IEEE Transac. Syst. Sci. Cybern. 4, 100–107 (1968)CrossRef P. Hart, N. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths. IEEE Transac. Syst. Sci. Cybern. 4, 100–107 (1968)CrossRef
5.
Zurück zum Zitat I. Millington, J. Funge, Artificial Intelligence for Games (Morgan Kaufmann Publishers, 2 edn., 2009) I. Millington, J. Funge, Artificial Intelligence for Games (Morgan Kaufmann Publishers, 2 edn., 2009)
6.
Zurück zum Zitat A. Botea, M. Muller, J. Schaeffer, Near optimal hierarchical path-finding. J. Game Dev. 1, 1–22 (2004) A. Botea, M. Muller, J. Schaeffer, Near optimal hierarchical path-finding. J. Game Dev. 1, 1–22 (2004)
7.
Zurück zum Zitat D. Ferguson, A. Stentz. Field D*: an interpolation-based path planner and replanner, in Proceedings of the International Symposium on Robotics Research (ISRR) (October 2005) D. Ferguson, A. Stentz. Field D*: an interpolation-based path planner and replanner, in Proceedings of the International Symposium on Robotics Research (ISRR) (October 2005)
8.
Zurück zum Zitat G. Ayorkor, A. Stentz, M. B. Dias, Continuous-field path planning with constrained path-dependent state variables, in ICRA 2008 Workshop on Path Planning on Costmaps (May 2008) G. Ayorkor, A. Stentz, M. B. Dias, Continuous-field path planning with constrained path-dependent state variables, in ICRA 2008 Workshop on Path Planning on Costmaps (May 2008)
9.
Zurück zum Zitat A. Nash, K. Daniel, S. Koenig, A. Felner. Theta*: any-angle path planning on grids, in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 1177–1183 (2007) A. Nash, K. Daniel, S. Koenig, A. Felner. Theta*: any-angle path planning on grids, in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 1177–1183 (2007)
10.
Zurück zum Zitat K. Daniel, A. Nash, S. Koenig, A. Felner, Theta*: any-angle path planning on grids. J. Artif. Intell. Res. 39, 533–579 (2010)MathSciNetMATH K. Daniel, A. Nash, S. Koenig, A. Felner, Theta*: any-angle path planning on grids. J. Artif. Intell. Res. 39, 533–579 (2010)MathSciNetMATH
11.
Zurück zum Zitat S. Choi, J.Y. Lee, and W. Yu. Fast any-angle path planning on grid maps with non-collision pruning. In IEEE International Conference on Robotics and Biomimetics, pages 1051–1056, Tianjin, China, December 2010 S. Choi, J.Y. Lee, and W. Yu. Fast any-angle path planning on grid maps with non-collision pruning. In IEEE International Conference on Robotics and Biomimetics, pages 1051–1056, Tianjin, China, December 2010
12.
Zurück zum Zitat P. Yap, Grid-based path-finding, in Advances in Artificial Intelligence, vol. 2338 of Lecture Notes in Computer Science, pp. 44–55 (Springer, Berlin, 2002) P. Yap, Grid-based path-finding, in Advances in Artificial Intelligence, vol. 2338 of Lecture Notes in Computer Science, pp. 44–55 (Springer, Berlin, 2002)
13.
Zurück zum Zitat M. Kanehara, S. Kagami, J. Kuffner, S. Thompson, H. Mizoguhi. Path shortening and smoothing of grid-based path planning with consideration of obstacles, in IEEE International Conference on Systems, Man and Cybernetics, ISIC, pp. 991–996 (October 2007) M. Kanehara, S. Kagami, J. Kuffner, S. Thompson, H. Mizoguhi. Path shortening and smoothing of grid-based path planning with consideration of obstacles, in IEEE International Conference on Systems, Man and Cybernetics, ISIC, pp. 991–996 (October 2007)
14.
Zurück zum Zitat C. E. Thorpe, L.H. Matthies. Path relaxation: path planning for a mobile robot, in OCEANS Conference, pp. 576–581 (September 1984) C. E. Thorpe, L.H. Matthies. Path relaxation: path planning for a mobile robot, in OCEANS Conference, pp. 576–581 (September 1984)
15.
Zurück zum Zitat P. Muñoz, M. D. R-Moreno, Improving efficiency in any-angle path-planning algorithms, in 6th IEEE International Conference on Intelligent Systems (IEEE-IS), pp. 213–218 (Sofia, Bulgaria, September 2012) P. Muñoz, M. D. R-Moreno, Improving efficiency in any-angle path-planning algorithms, in 6th IEEE International Conference on Intelligent Systems (IEEE-IS), pp. 213–218 (Sofia, Bulgaria, September 2012)
Metadaten
Titel
On Heading Change Measurement: Improvements for Any-Angle Path-Planning
verfasst von
Pablo Muñoz
María D. R-Moreno
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-14194-7_5