CFP last date
22 April 2024
Reseach Article

A Hybrid Framework for Robot Path Planning and Navigation using ACO and Dijkstra’s Algorithm

Published on October 2011 by Rebika Rai, Tejbanta Singh Chinghtam
International Symposium on Devices MEMS, Intelligent Systems & Communication
Foundation of Computer Science USA
ISDMISC - Number 9
October 2011
Authors: Rebika Rai, Tejbanta Singh Chinghtam
aeb9cc04-66e9-4a05-8217-938e3ed9c269

Rebika Rai, Tejbanta Singh Chinghtam . A Hybrid Framework for Robot Path Planning and Navigation using ACO and Dijkstra’s Algorithm. International Symposium on Devices MEMS, Intelligent Systems & Communication. ISDMISC, 9 (October 2011), 19-24.

@article{
author = { Rebika Rai, Tejbanta Singh Chinghtam },
title = { A Hybrid Framework for Robot Path Planning and Navigation using ACO and Dijkstra’s Algorithm },
journal = { International Symposium on Devices MEMS, Intelligent Systems & Communication },
issue_date = { October 2011 },
volume = { ISDMISC },
number = { 9 },
month = { October },
year = { 2011 },
issn = 0975-8887,
pages = { 19-24 },
numpages = 6,
url = { /proceedings/isdmisc/number9/3782-isdm195/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Symposium on Devices MEMS, Intelligent Systems & Communication
%A Rebika Rai
%A Tejbanta Singh Chinghtam
%T A Hybrid Framework for Robot Path Planning and Navigation using ACO and Dijkstra’s Algorithm
%J International Symposium on Devices MEMS, Intelligent Systems & Communication
%@ 0975-8887
%V ISDMISC
%N 9
%P 19-24
%D 2011
%I International Journal of Computer Applications
Abstract

The social insect metaphor for solving problems has become an emerging topic in the recent years. This approach emphasizes on direct or indirect interactions among simple agents. Swarm Intelligence offers an alternative way of designing intelligent systems. This paper explores the behavior of a group of mobile agents or robots to find the shortest path between the food (destination) and nest (source), without any visible, central, active coordination mechanism. Feedback by the agent during traversal of the path causes more agent concentration on the path, thereby influencing the behavior of the other agents and the indirect communication allows the agent to modify their environment to influence the behavior of other agents. Several obstacles are likely to be encountered in the course of this traversal. The objective of the agent is to find an appropriate and an optimize solution to bring itself closer to the goal considering the cost, time and path availability. A typical case of Traveling Salesman Problem (TSP) is incorporated to achieve this navigation problem wherein, an agent plans a route through a number of nodes and each node or location is only visited once with the agent returning back to city of origin. The Ant Colony Optimization (ACO) is a popular approach that searches for an optimal solution in a given set of solutions. Dijkstra’s Algorithm is an approach to find the shortest route between two locations. This paper addresses method of path finding problem using this two different approaches.

References
  1. Ryan Ward,” Optimizing Pheromone Modification for Dynamic Ant Algorithms”, TJHSST Senior Research Project (June 12, 2007)
  2. L.M. Gambardella and M. Dorigo,”Ant-Q: A Reinforcement Learning Approach to the TSP”, In Proceedings of Twelfth International Conference on Machine Learning, (1995).
  3. L.M. Gambardella and M. Dorigo,” Solving Symmetric and Asymmetric TSPs by Ant Colonies”, In Proceedings of IEEE International Conference on Evolutionary Computation, pages 622–627, (1996).
  4. Marco Dorigo, Vittorio Maniezzo and Alberto Colorni,”The Ant System: Optimization by a colony of cooperating agents”, In Proceedings of IEEE International Conference on Evolutionary Computation.
  5. A.P.Engelbrecht,”Computational Intelligence: An introduction”, Second Edn John Wiley & Sons, Ltd, (2007)
  6. Roland Siegwart and Illah R. Nourbakhsh,” Introduction to Autonomous Mobile Robots”, First Edn, MIT press.
  7. Angeniol, B., Vaubois, G de L C. and Texier JYL.(1988) ,”Self-Organizing Feature Maps and the Traveling Salesman Problem , Neural Networks”, Vol 1, pages289-293.
  8. Denis Darquennes, “Implementation and Applications of Ant Colony Algorithms”, Faculties Universitaires Notre-Dame de la Paix, Namur, Institute of Informatique Annee acad_emique (2004-2005)
  9. Gianni Di Caro, “Ant Colony Optimization and its Application to Adaptive Routing in Telecommunication Networks”, Bruxelles, September (2004)
  10. Beni, G., Wang, J.,”Swarm Intelligence in Cellular Robotic Systems”, Proceed. NATOAdvanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26–30 (1989).
  11. Ethan J. Tira-Thompson, Neil S. Halelamien, Jordan J. Wales, and David S. Touretzky,” Cognitive Primitives for Mobile Robots”, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15123-3891
  12. Yang Liu and Kavin M. Passino,”Swarm Intelligence: Literature review”, Deptt. Of Electrical Engineering, The Ohio state University, Columbus, March 30 (2000).
  13. Kyung min Han and Dr. Robert W. McLaren,” Collision Free Path Planning Algorithms for Robot Navigation Problem”, University of Missouri-Columbia, August (2007).
  14. Luo Xiong, Fan Xiao-ping, Yi Sheng, Zhang Heng,” A novel Genetic Algorithm for Robot Path Planning in Environment Containing Large Numbers of Irregular Obstacles”,Vol.26, No.1, January(2004).
  15. M. Youself Ibrahim and Allwyn Fernandes, “Study on Mobile Robot Navigation Techniques,” IEEE ICIT, Tunisia, December 8-10, (2004).
Index Terms

Computer Science
Information Sciences

Keywords

Pheromone Optimized path Navigation Path planning TSP ACO