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...

Full description

Saved in:
Bibliographic Details
Published in:International journal of control, automation, and systems 2021, Automation, and Systems, 19(1), , pp.491-504
Main Authors: Nagavarapu, Sarat Chandra, Vachhani, Leena, Sinha, Arpita, Buriuly, Somnath
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Control
Data exchange
Data structures
Engineering
Exploration
Fault tolerance
Graph theory
Graphical representations
Linear algebra
Mechatronics
Multiagent systems
Multiple robots
Robotics
Search methods
Unknown environments
제어계측공학
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1598-6446
2005-4092
DOI:10.1007/s12555-019-0067-8