Grant: Discovery Grants Program - Individual

Fault-tolerant search with multiple robots has attracted the attention of researchers in theoretical computer science and distributed computing. Group Search and Delivery are two important tasks arising from the need to design algorithms for multi-agent systems in distributed computing. I intend to design new algorithms and analyze tradeoffs involving time, mobility, and fault-tolerant communication for solving such tasks. The proposed algorithms will employ cooperating, communicating autonomous mobile agents in a distributed setting and operate over continuous as well as discrete domains. Proposed strategies will be fault-tolerant and maintain optimal characteristics despite hardware and/or software failures during their execution. Long term goal is to understand the impact of faulty agents on search and delivery. The general approach will be theoretical; research outcomes do not preclude the possibility that (some of) the resulting ideas will find useful applications in concrete practical situations. The underlying long term vision of the proposal is to determine how search times and competitive ratios depend on the number of agents involved, maximum number of faults that may occur, as well as type of agent fault and communication model. The basic approach will be first, to develop algorithms to solve a specific problem with given parameters, second develop lower bounds for the same problem by changing the related parameter(s) (e.g., number of faults, communication model), and third compare the resulting bounds. (This can be very challenging by itself.) Next, there will be a systematic approach in that I will attempt to capture general principles by proceeding from the special to the more general solutions. In this part existing research studies/solutions will be taken into account. Techniques will be used from theoretical computer science (algorithm design, distributed and mobile agent computing) and relevant mathematical fields (probability theory, graph theory, combinatorial optimization). My hope is to develop a hierarchy of search (patrolling, gathering) times parametrized by the number of faults, number of robots, type of communication model, domain, etc. This will make possible to compare the computational power of the models with respect to the problems proposed. I believe that this will be a significant contribution in this area. To date there has been very little systematic study and analysis of the impact of faulty communication on group-search. Prior research on search addressed mostly questions without resort to a communication model involving faulty agents. A novel contribution of our proposed research will be to bring to the forefront the communication capabilities of the agents and combine fundamental ideas of Combinatorial Optimization, Distributed Computing, and Algorithm Analysis in a systematic manner in order to provide more efficient algorithms for group search.