A time competitive heterogeneous multi robot path finding algorithm

We investigate the path finding problem to a target whose position is known in an unknown and unbounded environment. We present a novel motion planning algorithm which uses a group of heterogeneous robots to search for the path to the target. The algorithm assigns the robots in pairs, each two robots within a pair have the same velocity, and are cooperating to search for the path to the target. The algorithm artificially bounds each pair´s search to an ellipse whose focal points are the start and the target points. Each robot pair has a different velocity, thus each pair is assigned to an ellipse with an area corresponding to the search time according to its velocity. The algorithm´s performance is analyzed using time competitiveness definitions, and its upper bound is proved to be quadratic in the optimal off-line solution. The algorithm is complete and robust.