Abstract
In robotics, more precisely Autonomous Mobile Robotics (AMR), robots, much like human beings, are confronted regularly with the problem of finding the best path to take from a source location to a destination location. This is an optimization concern, since the robot wants to minimize its cost in time or in energy while achieving its goal. Different algorithms exist for shortest path computation; the famous Dijkstra’s Shortest Path Algorithm will solve single-source shortest path problems in near linear time (O(mn log n)). However, for certain complex optimization path-planning problems, this algorithm alone is insufficient. We will study a dynamical formulation using Integer Programming (IP) to solve complex path-planning problems in robotics.
Faculty Advisor Name
Randall Pyke
Faculty Advisor Institution
University of Toronto
Suggested Mathematics Subject Classification(s)
90C10, 90B06
Recommended Citation
Martin Talbot, A Dynamical Programming Solution for Shortest Path Itineraries in Robotics, Furman University Electronic Journal of Undergraduate Mathematics, 9 (2016), 21-35. Available at: https://scholarexchange.furman.edu/fuejum/vol9/iss1/2
Comments
This paper was written while the author was an undergraduate at Ryerson University. The author would like to thank Randall Pyke for his support and generosity.