Real-time pathfinding algorithms in practical application

• Autorzy: Pochmara J , Grygiel W

Warianty tytułu

PL

Algorytmy czasu rzeczywistego do poszukiwania drogi w zastosowaniu praktycznym

• Języki publikacji: EN

Abstrakty

EN

Due to the fact that the A* algorithm is very flexible, can be used in a variety of situations, it became the main algorithm used in our study. Its biggest drawback is the need for large amounts of memory to store all the surveyed points. This problem greatly increases with the increase in the study area. However, the A* algorithm allows the robots to make efficient decisions on how to move from the starting to the ending point. Because of this, the A* algorithm should be taken into account as an option for pathfinding for intelligent robots.

PL

Ze względu na to, że Algorytm A* jest bardzo elastyczny, można go stosować różnych sytuacjach, stał się on głównym algorytmem wykorzystywanym podczas naszych badań. Jego największą wadą jest potrzeba dużej ilości pamięci w celu zapamiętania wszystkich zbadanych punktów. Ten problem znacznie się nasila wraz ze wzrostem badanego obszaru. Jednak algorytm A* pozwala robotom na podejmowanie sprawnych decyzji co do sposobu poruszania się od punktu startowego do końcowego. Z tego powodu warto brać algorytm A* pod uwagę jako opcję dla poszukiwania dróg przez inteligentne roboty.

Słowa kluczowe

EN

search algorithms; pathfinding; A-Star; A* algorithm

PL

algorytmy poszukiwania drogi; poszukiwanie drogi; astar; algorytm A*

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2013
• Tom: Vol. 54, nr 12
• Strony: 9--13
• Opis fizyczny: Bibliogr. 26 poz., wykr.

Twórcy

autor

Pochmara J

• Poznan University of Technology, Chair of Computer Engineering Poznan, Poland

autor

Grygiel W

• Poznan University of Technology

Bibliografia

• [1] Elfes A.: “Sonar-based real-world mapping and navigation,” Robotics and Automation, IEEE Journal of , vol. 3, no. 3, pp. 249–265, June 1987.
• [2] Avnaim F., Boissonnat J.D., Faverjon B.: “A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles,” Robotics and Automation, 1988. Proceedings., 1988 IEEE International Conference on , vol., no., pp. 1656–1661 vol. 3, 24–29 Apr 1988.
• [3] Murphy R.: Introduction to AI robotics, “Navigation”, MIT Press, 2000.
• [4] Burdziuk A., Pochmara J., Lakomy K., Szablata P., Koppa R.: “Realtime physics engine for robots movement,” Mixed Design of Integrated Circuits and Systems (MIXDES), 2012 Proceedings of the 19th International Conference , vol., no., pp. 511–515, 24–26 May 2012.
• [5] Sheu P., Xue Q.: Intelligent robotic planning systems, Robot Path Planning, World Scientific Publishing Co., 1993.
• [6] Cook G.: Mobile Robots: Navigation, Control and Remote SensingRobot Navigation, John Wiley & Sons, Inc., 2011.
• [7] Lee C.Y.: “An Algorithm for Path Connections and Its Applications,” Electronic Computers, IRE Transactions on, vol. EC -10, no. 3, pp. 346–365, Sept. 1961.
• [8] Akers, Sheldon B.: “A Modification of Lee’s Path Connection Algorithm,” Electronic Computers, IEEE Transactions on , vol. C-16, no. 1, pp. 97–98, Feb. 1967.
• [9] Didier K., Jo D.: “A flexible path generator for a mobile robot,” Advanced Robotics, 1991. ‘Robots in Unstructured Environments’, 91 IC AR., Fifth International Conference on , vol., no., pp. 1069–1073 vol. 2, 19–22 June 1991.
• [10] Arkin R.: “Motor schema based navigation for a mobile robot: An approach to programming by behavior,” Robotics and Automation. Proceedings. 1987 IEEE International Conference on, vol. 4, no., pp. 264–271, Mar 1987.
• [11] Marco Dorigo, Vittorio Maniezzo, and Alberto Colomi, “The Ant. System: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, vol. 26, no. 1, pp. 1–13, 1996.
• [12] Liu Wei, Zhou Yuren: “An Effective Hybrid Ant Colony Algorithm for Solving the Traveling Salesman Problem,” Intelligent Computation Technology and Automation (ICICT A), 2010 International Conference on, vol. 1, no., pp. 497–500, 11–12 May 2010.
• [13] Wen-liang Zhong, Jun Zhang, “A novel discrete particle swarm optimization to solve traveling salesman problem”, 2007 IEEE Congress on Evolutionary Computation (CEC 2007).
• [14] Jasika N., Alispahic N., Elma A., Ilvana K., Elma L., Nosovic N.: “Dijkstra’s shortest path algorithm serial and parallel execution performance analysis,” MIPRO , 2012 Proceedings of the 35th International Convention, vol., no., pp. 1811–1815, 21–25 May 2012.
• [15] Hwan II Kang, Byunghee Lee, Kabil Kim: “Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm,” Computational Intelligence and Industrial Application, 2008. PACII A ‘08. Pacific-Asia Workshop on , vol. 2, no., pp. 1002–1004, 19–20 Dec. 2008.
• [16] Hart P.E., Nilsson N.J., Raphael B.: “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” Systems Science and Cybernetics, IEEE Transactions on, vol. 4, no. 2, pp. 100–107, July 1968.
• [17] G. Gordon S., Thrun M., Likhachev ARA*: Anytime A* with Provable Bounds on Sub-Optimality, pp. 8, School of Computer Science Carnegie Mellon University Pittsburgh.
• [18] Trovato K.I.: “Differential A*: an adaptive search method illustrated with robot path planning for moving obstacles and goals, and an uncertain environment,” Tools for Artificial Intelligence, 1989. Architectures, Languages and Algorithms, IEEE International Workshop on , vol., no., pp. 624–639, 23–25 Oct 1989.
• [19] DUAN Li-qiong, ZHU Jian-jun, WANG Qing-she, MA Ling. Fast Realization of the Improved A* Algorithm for Shortest Route. HYDRO GRAPHIC SURVEYIN G AND CHARTIN G. Vol. 24, No. 5. Sep, 2004, p. 20–22.
• [20] Khantanapoka K., Chinnasarn K.: “Pathfinding of 2D & 3D game.
• [21] Real-time strategy with depth direction A* algorithm for multi-layer,” Natural Language Processing, 2009. SNLP ‘09. Eighth International Symposium on , vol., no., pp. 184–188, 20–22 Oct. 2009.
• [22] Millington I., Funge J.: Artificial Intelligence for Games, 2.2.2 Heuristics, Evlsevier Morgan Kaufmann, Inc., 2009.
• [23] Bourg D., Seemann G.: Al for game developers, A* Pathfinding, O’Reilly Media, Inc., 2004.
• [24] Blaich M., Rosenfelder M., Schuster M., Bittel O., Reuter J.: “Fast grid based collision avoidance for vessels using A* search algorithm,” Methods and Models in Automation and Robotics (MMAR), 2012, 17th International Conference on , vol., no., pp. 385–390, 27–30 Aug. 2012.
• [25] Nordin N.A.M., Zaharudin Z.A., Maasar M.A., Nordin N.A.: “Finding shortest path of the ambulance routing: Interface of A* algorithm using C# programming,” Humanities, Science and Engineering Research (SHUSER ), 2012 IEEE Symposium on , vol., no., pp. 1569–1573, 24–27 June 2012.
• [26] Tournassoud P., Jehl O.: “Motion planning for a mobile robot with a kinematic constraint,” Robotics and Automation, 1988. Proceedings., 1988 IEEE International Conference on , vol., no., pp. 1785–1790, vol. 3, 24–29 Apr 1988.