A Dynamical Programming Solution for Shortest Path Itineraries in Robotics

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.