A Time Competitive Heterogeneous Multi Robot Path Finding Algorithm

Abstract — 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. I