Low-cost robots are characterized by low computational resources and limited energy supply. Path planning algorithms aim to find the optimal path between two points so the robot consumes as little energy as possible. However, these algorithms were not developed considering computational limitations ( i.e., processing and memory capacity). This paper presents the HCTNav path-planning algorithm (HCTLab research group’s navigation algorithm). This algorithm was designed to be run in low-cost robots for indoor navigation. The results of the comparison between HCTNav and the Dijkstra’s algorithms show that HCTNav’s memory peak is nine times lower than Dijkstra’s in maps with more than 150,000 cells.
References
[1]
Fu, L.; Sun, D.; Rilett, L.R. Heuristic shortest path algorithms for transportation applications: State of the art. Comput. Oper. Res. 2006, 33, 3324–3343, doi:10.1016/j.cor.2005.03.027.
[2]
Antich, J.; Ortiz, A.; Minguez, J. A Bug-Inspired Algorithm for Efficient Anytime Path Planning. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MO, USA, 10–15 October 2009; pp. 5407–5413.
[3]
Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. Dijkstra’s Algorithm. In Introduction to Algorithms, 2nd ed. ed.; MIT Press: Cambridge, MA, USA, 2001; pp. 595–601.
[4]
Idris, M.; Bakar, S.; Tamil, E.; Razak, Z.; Noor, N. High-Speed Shortest Path Co-Processor Design. In Proceedings of Third Asia International Conference on Modelling & Simulation, Bali, Indonesia, 25–29 May 2009; pp. 626–631.
[5]
Cain, T. Practical Optimizations for A* Path Generation. In AI Game Programming Wisdom, 2nd ed. ed.; Charles River Editors: Boston, MA, USA, 2003; pp. 146–152.
[6]
Grant, K.; Mould, D. Combining Heuristic and Landmark Search for Path Planning. In Proceedings of the Confereunce on Futre Play: Research, Play, Share, Toronto, ON, Canada, 3–5 November 2008; pp. 9–16.
[7]
Goto, T.; Kosaka, T.; Noborio, H. On the Heuristics of A* or A Algorithm in ITS and Robot Path Planning. In Proceedings of IEEE/RSJ International Conference on Intelligent Robot and Systems, Las Vegas, NV, USA, 27–31 October 2003; pp. 1159–1166.
[8]
Bollobas, B. Modern Graph Theory; Springer: Heidelberg, Germany, 1998; pp. 252–259.
[9]
Selamat, A.; Zolfpour-Arokhlo, M.; Hashim, S.Z. A Fast Path Planning Algorithm for Route Guidance System. In Proceedings of IEEE International Conference on Systems, Man and Cybernetics, Anchorage, AK, USA, 9–12 October 2011; pp. 2773–2778.
[10]
Langerwisch, M.; Wagner, B. Dynamic Path Planning for Coordinated Motion of multiple Mobile Robots. In Proceedings of IEEE International Conference on Intelligent Transportation Systems, Washington, DC, USA, 5–7 October 2011; pp. 1989–1994.
[11]
Zhou, J.; Lin, H. A Self-Localization and Path Planning Technique for Mobile Robot Navigation. In Proceedings of the Intelligent Control and Automation (WCICA), Taipei, China, 21–25 June 2011; pp. 694–699.
[12]
Abdul-Jabbar, J.M.; Alwan, M.A.; Al-ebadi, M. A new hardware architecture for parallel shortest path searching processor based-on FPGA technology. Int. J. Electron. Comput. Sci. Eng. 2012, 1, 2572–2582.
[13]
Jiang, Z.; Wu, J. On Achieving the Shortest-Path Routing in 2-D Meshes. In Proceedings of the Parallel and Distributed Processing Symposium, Long Beach, CA, USA, 26–30 March 2007; pp. 26–30.
[14]
Lumelsky, V.J.; Stepanov, A. Path-planning strategies for a point mobile automaton moving amidst obstacles of arbitrary shape. Algorithmica 1987, 2, 403–430, doi:10.1007/BF01840369.
[15]
Lumelsky, V.J.; Skewis, T. Incorporating range sensing in the robot navigation function. IEEE Trans. Syst. Man Cybern. 1990, 2, 1058–1068, doi:10.1109/21.59969.
[16]
Kamon, I.; Rivlin, E. Sensory-based motion planning with global proofs. IEEE Trans. Robot. Autom. 1997, 13, 814–822, doi:10.1109/70.650160.
[17]
Knudson, M.; Tumer, K. Adaptive navigation for autonomous robots. Auton. Robots 2011, 59, 410–420, doi:10.1016/j.robot.2011.02.004.
[18]
Sharef, S.M.; Sa’id, W.K.; Khoshaba, F.S. A Rule-Based System for Trajectory Planning of an Indoor Mobile Robot. In Proceedings of the International Multi-Conference on Systems Signals and Devices, Amman, Jordan, 27–30 June 2010; pp. 1–7.
[19]
Yu, N.; Ma, C. Mobile Robot Map Building Based on Cellular Automata. In Proceedings of the Pacific-Asia Conference on Circuits, Communications and System, Wuhan, China, 17–18 July 2011; pp. 1–4.
[20]
Gonzalez-Arjona, D.; Sanchez, A.; de Castro, A.; Garrido, J. Occupancy-Grid Indoor Mapping Using FPGA-Based Mobile Robots. In Proceedings of the Conference on Design of Circuits and Integrated Systems, Albufeira, Portugal, 16–18 November 2011; pp. 345–350.
[21]
Buckland, M. Programming Game AI by Example, 1st ed. ed.; Wordware Publishing: Plano, TX, USA, 2005; pp. 193–248.
[22]
Bresenham, J.E. Algorithm for computer control of a digital plotter. IBM Syst. J. 1965, 4, 25–30, doi:10.1147/sj.41.0025.
