[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

A fast two-stage ACO algorithm for robotic path planning

  • ISNN 2011
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

Ant colony optimization (ACO) algorithms are often used in robotic path planning; however, the algorithms have two inherent problems. On one hand, the distance elicitation function and transfer function are usually used to improve the ACO algorithms, whereas, the two indexes often fail to balance between algorithm efficiency and optimization effect; On the other hand, the algorithms are heavily affected by environmental complexity. Based on the scent pervasion principle, a fast two-stage ACO algorithm is proposed in this paper, which overcomes the inherent problems of traditional ACO algorithms. The basic idea is to split the heuristic search into two stages: preprocess stage and path planning stage. In the preprocess stage, the scent information is broadcasted to the whole map and then ants do path planning under the direction of scent information. The algorithm is tested in maps of various complexities and compared with different algorithms. The results show the good performance and convergence speed of the proposed algorithm, even the high grid resolution does not affect the quality of the path found.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

Explore related subjects

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

References

  1. Dorigo M, Maniezzo Colomi V (1996) Antsystem: optimization by a colony of cooperating agents. IEEE Trans SMC 26(1):28–41

    Google Scholar 

  2. Deneubourg J.-L, Clip P.–L, Camazine SS (1994) Ants, buses and robots-self-organization of transportation systems. Percept Act 12–23

  3. Xiaoping F, Xiong L, Sheng Y, Shengyue Y, Heng Z (2003) Optimal path planning for mobile robots based on intensified ant colony optimization algorithm. IEEE Robat Intel Syst Sig Proc 1:131–136

    Google Scholar 

  4. Liu S, Mao L, Yu J (2006) Path planning based on ant colony algorithm and distributed local navigation for multi-robot systems. In: IEEE international conference on mechatronics and automation, pp 1733–1738

  5. Lv N, Zuren F (2006) Numerical potential field and ant colony optimization based path planning in dynamic environment. IEEE WCICA’06 2:8966–8970

    Google Scholar 

  6. Zhu B, Zhang Y (2005) An ant colony algorithm based on grid method for mobile robot path planning. Robot 02

  7. Fan X, Luo X, Yi S, Hang Z (2004) Path planning for robots based on ant colony optimization algorithm under complex environment. Contr Dec 19(2)

  8. Chen X, Zhao Y, Han J (2007) An improved ACO_based robotics path planning method. J Contr Thory Appl

  9. Chen X, Fang X, Han J (2008) An alarm pheromone based ACO method for path planning. Contr Dec

  10. Dorigo G (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem [R]. IEEE Trans Evol Comput 1(1):53–56

    Article  Google Scholar 

  11. Ying-Tung H, Cheng-Long C, Cheng-Chih C (2004) Ant colony optimization for best path planning. IEEE/ISCIT’04 109–113

  12. Yue F, Cui P, Cui H (2006) Planetary rover path-planning based on ant colony optimization algorithm. Contr Dec 12

  13. Mei H, Tian Y, Zu L (2006) A hybrid ant colony optimization algorithm or path planning of robot in dynamic environment. Int J Infor Technol 12(3):78–88

    Google Scholar 

  14. Tan X, Chen D (2009) A hybrid approach of path planning for mobile robots based on the combination of ACO and APF algorithms. In: Intelligent systems and applications, pp 1–4

  15. Mohamad MM, Dunnigan MW, Taylor NK (2005) Ant colony robot motion planning. Proc Int Conf EUROCON’05 1:213–216

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Intelligent Control Research Lab, Fudan University, Shanghai, China

    Xiong Chen, Yingying Kong & Xiang Fang

  2. Center of CIMS, Tongji University, Shanghai, China

    Qidi Wu

Authors
  1. Xiong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yingying Kong
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiang Fang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Qidi Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiong Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, X., Kong, Y., Fang, X. et al. A fast two-stage ACO algorithm for robotic path planning. Neural Comput & Applic 22, 313–319 (2013). https://doi.org/10.1007/s00521-011-0682-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-011-0682-7

Keywords

Search

Navigation