Heuristic-Based Dynamic Route Planning Method for a Homogeneous Multi-robot Team

Abstract

Multi-robot systems have recently received a great deal of attention due to the ability to perform an assigned task in a more reliable, faster and cheaper way beyond what is possible with a single robot. However, they may have some drawbacks, such as obstruction among robots during a task. Non-intersecting tours are preferable for the robots to prevent obstruction. Moreover, after an initial plan, the environment (open roads may be closed) and/or task requests (active/deactive) may change dynamically, which may require a fast tour construction for the members of the mobile robot group. In this study, a novel heuristic method is proposed to construct non-intersecting tours for the members of a mobile robot group in dynamic and/or partially unknown environments considering the energy capacities of the robots. It is an aggregate algorithm consisting of the Savings algorithm and the Sweep algorithm, and is applicable to the problems that are modeled using complete, sparse, directed or undirected networks. Simulations are offered to show the effectiveness of the proposed algorithm.