Mobile robot routing with dynamic programming

The rise of automated manufacturing systems, and autonomous systems in general, is creating a need for increased intelligence in mobile robotic devices, also known as autonomous guided vehicles (AGVs). One of the most important tasks these vehicles must perform is routing their own path in a cluttered environment. The path must ensure that obstacles are avoided without any unnecessary distance being covered. This paper discusses an approach to solving this routing problem. The method employed digitizes the workspace into a grid of nodes and treats the grid as a transition network. The principles of dynamic programming, with slight modifications, can be used to generate paths through this network that exhibit the desired degree of collision avoidance and economy. The algorithm is quick and simple enough to be executed by an on-board microprocessor, and it can be updated whenever the environment changes. The general principles are discussed, both of dynamic programming in general and of its modifications to fit the AGV routing problem. Two examples are then presented. The first example is generated with the emphasis on creating as short a path as possible, and the second includes a trade-off between path shortness and safety.