Statistic Methods for Path-Planning Algorithms Comparison | KI - Künstliche Intelligenz Skip to main content
Springer Nature Link
Log in

Statistic Methods for Path-Planning Algorithms Comparison

  • Technical Contribution
  • Published:
KI - Künstliche Intelligenz Aims and scope Submit manuscript

Abstract

The path-planning problem for autonomous mobile robots has been addressed by classical search techniques such as A* or, more recently, Theta* or S-Theta*. However, research usually focuses on reducing the length of the path or the processing time. The common practice in the literature is to report the run-time/length of the algorithm with means and, sometimes, some dispersion measure. However, this practice has several drawbacks, mainly due to the loose of valuable information that this reporting practice involves such as asymmetries in the run-time, or the shape of its distribution. Run-time analysis is a type of empirical tool that studies the time consumed by running an algorithm. This paper is an attempt to bring this tool to the path-planning community. To this end the paper reports an analysis of the run-time of the path-planning algorithms with a variety of problems of different degrees of complexity, indoors, outdoors and Mars surfaces. We conclude that the time required by these algorithms follows a lognormal distribution.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. All the code, scripts and datasets required to repeat these experiments are available on http://atc1.aut.uah.es/~david/datasets.php#ki2013.

  2. The execution was done on a 2 GHz Intel Core i7 with 4 GB of RAM under Ubuntu 10.10 (64 bits).

  3. DTM of MSL Landing Site in Gale Crater can be obtained at https://hirise.lpl.arizona.edu/dtm/dtm.php?ID=ESP_023957_1755.

References

  1. Millington I, Funge J (2009) Artificial intelligence for games, 2nd edn. Morgan Kaufmann, San Mateo

    Google Scholar 

  2. Ferguson D, Stentz A (2005) Field D*: an interpolation-based path planner and replanner. In: Proceedings of the international symposium on robotics research (ISRR), October 2005

    Google Scholar 

  3. Nash A, Daniel K, Koenig S, Felner A (2007) Theta*: any-angle path planning on grids. In: Proceedings of the AAAI conference on artificial intelligence (AAAI), pp 1177–1183

    Google Scholar 

  4. Munoz P, R-Moreno MD (2012) S-Theta*: low steering path-planning algorithm. In: Proc of the thirty-second SGAI international conference on artificial intelligence, Cambridge, UK, December 2012

    Google Scholar 

  5. Munoz P, R-Moreno MD (2012) Improving efficiency in any-angle path-planning algorithms. In: 6th IEEE international conference on intelligent systems IS’12, Sofia, Bulgaria, September 2012

    Google Scholar 

  6. Choi S, Lee JY, Yu W (2010) Fast any-angle path planning on grid maps with non-collision pruning. In: IEEE international conference on robotics and biomimetics, Tianjin, China, December 2010, pp 1051–1056

    Google Scholar 

  7. Daniel K, Nash A, Koenig S, Felner A (2010) Theta*: any-angle path planning on grids. J Artif Intell Res 39:533–579

    MathSciNet  MATH  Google Scholar 

  8. Botea A, Muller M, Schaeffer J (2004) Near optimal hierarchical path-finding. J Game Dev 1:1–22

    Google Scholar 

  9. Yap P (2002) Grid-based path-finding. In: Advances in artificial intelligence. Lecture notes in computer science, vol 2338. Springer, Berlin, pp 44–55

    Chapter  Google Scholar 

  10. Ayorkor G, Stentz A, Dias MB (2008) Continuous-field path planning with constrained path-dependent state variables. In: ICRA 2008 workshop on path planning on costmaps, May 2008

    Google Scholar 

  11. Bresenham J (1965) Algorithm for computer control of a digital plotter. IBM Syst J 4:25–30

    Article  Google Scholar 

  12. Hoos H, Stützle T (1998) Evaluating Las Vegas algorithms—pitfalls and remedies. In: Proceedings of the fourteenth conference on uncertainty in artificial intelligence (UAI-98). Morgan Kaufmann, San Mateo, pp 238–245

    Google Scholar 

  13. Hoos H, Stützle T (2000) Local search algorithms for SAT: an empirical evaluation. J Autom Reason 24(4):421–481

    Article  MATH  Google Scholar 

  14. Barr R, Hickman B (1993) Reporting computational experiments with parallel algorithms: issues, measures, and experts’ opinions. ORSA J Comput 5:2

    Article  MATH  Google Scholar 

  15. Hoos H, Stützle T (1998) Characterizing the run-time behavior of stochastic local search. In: Proceedings AAAI99

    Google Scholar 

  16. Hoos H, Stützle T (1999) Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artif Intell 112(1–2):213–232

    Article  MATH  Google Scholar 

  17. Chiarandini M, Stützle T (2002) Experimental evaluation of course timetabling algorithms. Intellectics Group, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany. Tech Rep AIDA-02-05

  18. Frost D, Rish I, Vila L (1997) Summarizing CSP hardness with continuous probability distributions. In: Proceedings of the fourteenth national conference on artificial intelligence and ninth conference on innovative applications of artificial intelligence (AAAI’97/IAAI’97). AAAI Press, New York, pp 327–333

    Google Scholar 

  19. Epstein S, Yun X (2010) From unsolvable to solvable: an exploration of simple changes. In: Workshops at the twenty-fourth AAAI conference on artificial intelligence

    Google Scholar 

  20. Barrero DF, Castaño B, R-Moreno MD, Camacho D (2011) Statistical distribution of generation-to-success in GP: application to model accumulated success probability. In: Proceedings of the 14th European conference on genetic programming (EuroGP 2011), Turin, Italy, 27–29 Apr 2011. LNCS, vol 6621. Springer, Berlin, pp 155–166

    Google Scholar 

Download references

Acknowledgements

Pablo Muñoz is supported by the European Space Agency (ESA) under the Networking and Partnering Initiative (NPI) Cooperative systems for autonomous exploration missions. This work was partially supported by the Spanish CDTI project colsuvh, leaded by the Ixion Industry and Aerospace company.

Author information

Authors and Affiliations

  1. Departamento de Automática, Universidad de Alcalá, Madrid, Spain

    Pablo Muñoz, David F. Barrero & María D. R-Moreno

Authors
  1. Pablo Muñoz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David F. Barrero
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. María D. R-Moreno
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pablo Muñoz.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Muñoz, P., Barrero, D.F. & R-Moreno, M.D. Statistic Methods for Path-Planning Algorithms Comparison. Künstl Intell 27, 201–211 (2013). https://doi.org/10.1007/s13218-013-0257-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13218-013-0257-0

Keywords

Search

Navigation