Generalizing Multi-agent Graph Exploration Techniques

The system of multiple agents working in coordination for a given task has several advantages on faster completion, fault-tolerance, etc. To develop a multi-agent graph exploration technique, the following are defined: 1) the way agents communicate, 2) initial placement of agents and 3) the role of each agent in a systematic search of (unexplored) vertices/edges in the graph. However, the general concepts and requirements are not developed. Hence, we attempt to generalize the multi-agent system for graph exploration. The graph may or may not be known a priori. The proposed representation for the multi-agent system is aimed to provide general conditions for declaring completion and finite time completion applicable to any multi-agent system for graph exploration. Results are proved using linear algebraic concepts on graphs. We also propose modifications in the incidence matrix as a data structure for organized information exchange between the agents. Further, a generic algorithm for the system of multiple agents exploring a graph is developed. The algorithm is based on the proposed generalized framework and modified incidence matrix. Simulation videos show the applicability of proposed generalization in exploring a graph using multiple agents for various combinations of initial placements of agents, search strategy, and interagent communication method. Further, We use the generalization to show the application of the proposed method in multi-robot exploration and map building of an unknown environment represented by a graph.