Optimal multi-agent traversal algorithms for trees and rings

摘要

This paper introduces the multi-agent traversal problem: the problem to find a travel schedule of each mobile agent so that each agent can visit all nodes and return to its originating node. The problem requires us to find the schedule with the minimum travel time under the constraint that no two agents can simultaneously occupy a node. The problem is clearly NP-hard in arbitrary networks. This paper considers the problem for trees and rings and presents the optimal traversal plans of n agents in these networks, where n is the number of nodes in a network.