Task-level tour plan generation for mobile robots

Abstract

A tour plan generator (TPG) specifically adapted for mobile robots is described. The TPG computes the itinerary of a tour passing through a number of locations. One typical constraint is that a single-armed mobile robot is usually unable to carry more than one object at a time in its gripper. This constraint requires the TPG to generate a tour in which each pick-up location is visited immediately prior to the corresponding drop-off location. A model that makes it possible to reduce this problem to a special case of the traveling salesman problem with asymmetric cost matrix and nonEuclidean distances is introduced. Another constraint in many mobile robots is the need to periodically visit a home location. The TPG introduced here automatically creates multiple subtours such that a predefined maximal length for each subtour is not exceeded. The algorithm obtains near-optimal solutions with short computation times by combining different heuristic tour-construction rules into a heuristic team approach.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>