Nested Monte Carlo Search (NMCS) has numerous applications, ranging from chemical retrosynthesis to quantum circuit design. We propose a generalization of NMCS that we named Nested Depth Search (NDS), in which a fixed depth search is used during a higher-level playout to generate the states sent to lower-level exploration. We establish the runtime of NDS and provide algorithms to compute the exact probability distribution of sequences generated by NDS. Experiments with the Set Cover problem and the Multiple Sequence Alignment problem show that NDS outperforms NMCS with the same time budget

The Connected Multi-Agent Path Finding (CMAPF) problem asks for a plan to move a group of agents in a graph while respecting a connectivity constraint. We study a generalization of CMAPF in which the graph is not entirely known in advance, but is discovered by the agents during their mission. We present a framework introducing this notion and study the problem of searching for a strategy to reach a configuration in this setting. We prove the problem to be PSPACE-complete when requiring all agents to be connected at all times, and NEXPTIME-hard in the decentralized case.

The Connected Multi-Agent Path Finding (CMAPF) problem asks for a plan to move a group of agents in a graph while respecting a connectivity constraint. We study a generalization of CMAPF in which the graph is not entirely known in advance, but is discovered by the agents during their mission. We present a framework introducing this notion and study the problem of searching for a strategy to reach a configuration in this setting. We prove the problem to be PSPACE-complete when requiring all agents to be connected at all times, and NEXPTIME-complete in the decentralized case, regardless of whether we consider a bound on the length of the execution.

Path planning is the task of devising a sequence steps for a mobile entity to follow. This task is required at the center of numerous real-world problems. The study of autonomous planning can allow one to reduce congestion, pollution, accidents, costs and more. In some applications, it is important to consider the connectivity of the agents. Although some settings guarantee a permanent connectivity among entities (e.g. warehouses), this is not always true in applications with open environments. Another aspect that can be found in many applications is the lack of complete knowledge of the area in which the entities move. For instance, in exploration missions, the agents are not provided any information of the environment and must discover it by themselves. Recent works on the planning of entities have been focused on the planning of collision-free executions. This problem, called Multi-Agent Path Finding (MAPF), is to find a sequence of steps for a group of agents to reach specified targets while avoiding collisions. The contribution of this work is twofold. First, we present a framework to study and model connectivity-based multi-agent path planning problems. We provide a detailed initial work on the complexity of this framework and an optimal algorithm to solve it. Second, we extend our connectivity framework to the incomplete knowledge setting and show the complexity of the connected and decentralized computation of plans under partially known environments.

We present a generic tool to visualize missions of the Connected Multi-Agent Path Finding (CMAPF) problem. This problem is a variant of MAPF which requires a group of agents to navigate from an initial configuration to a goal configuration while maintaining connection. The user can create an instance of CMAPF and can play the generated plan. Any algorithm for CMAPF can be plugged into the tool.

We study a variant of the multi-agent path finding (MAPF) problem in which the group of agents are required to stay connected with a supervising base station throughout the execution. In addition, we consider the problem of covering an area with the same connectivity constraint. We show that both problems are PSPACE-complete on directed and undirected topological graphs while checking the existence of a bounded plan is NP-complete when the bound is given in unary (and PSPACE-hard when the encoding is in binary). Moreover, we identify a realistic class of topological graphs on which the decision problem falls in NLOGSPACE although the bounded versions remain NP-complete for unary encoding.

Motivated by the increasing appeal of robots in information-gathering missions, we study multiagent path planning problems in which the agents must remain interconnected. We model an area by a topological graph specifying the movement and the connectivity constraints of the agents. We study the theoretical complexity of the reachability and the coverage problems of a fleet of connected agents on various classes of topological graphs. We establish the complexity of these problems on known classes, and introduce a new class called sight-moveable graphs which admit efficient algorithms.

We present a tool for graph coverage with a fleet of UAVs. The UAVs must achieve the coverage of an area under the constraint of staying connected with the base, where the mission supervisor starts the plan. With an OpenStreetMap interface, the user is able to choose a specific location at which the mission needs to be generated and to observe the resulting plan being executed.