Arthur Queffelec

AAAI Conference 2026 Conference Paper

Nested Depth Search

• Junkang Li
• Tristan Cazenave
• Swann Legras
• Arthur Queffelec
• Veronique Ventos

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.

TCS Journal 2023 Journal Article

Complexity of planning for connected agents in a partially known environment

• Arthur Queffelec
• Ocan Sankur
• François Schwarzentruber

IJCAI Conference 2021 Conference Paper

Connect Multi-Agent Path Finding: Generation and Visualization

• Arthur Queffelec
• Ocan Sankur
• Francois Schwarzentruber

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.

JAAMAS Journal 2020 Journal Article

Complexity of planning for connected agents

• Tristan Charrier
• Arthur Queffelec
• François Schwarzentruber

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

IJCAI Conference 2019 Conference Paper

Reachability and Coverage Planning for Connected Agents

• Tristan Charrier
• Arthur Queffelec
• Ocan Sankur
• François Schwarzentruber

Motivated by the increasing appeal of robots in information-gathering missions, we study multi-agent 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.

AAMAS Conference 2019 Conference Paper

Reachability and Coverage Planning for Connected Agents

• Tristan Charrier
• Arthur Queffelec
• Ocan Sankur
• François Schwarzentruber

Unmanned autonomous vehicle assisted information gathering missions have quickly picked up interest. Indeed, the advances on drones are making this type of missions possible. Thus, we study multi-agent path planning problems, namely reachability and coverage, for such missions with a connectivity constraint. This version of the multi-agent path planning asks to generate a plan, a sequence of steps, for a group of agents that are to stay connected during the missions while satisfying the specified goal. In this paper, we study the complexity of the coverage and reachability problems for a cooperation of agents with a connectivity constraint which restrain their movement. We identify a class of topological graphs which allows one to reduce the complexity of the decision problems from PSPACE-complete to LOGSPACE. We show, on the other hand, that the bounded versions of the previous problems are NP-complete.

IJCAI Conference 2018 Conference Paper

Generating Plans for Cooperative Connected UAVs

• François Bodin
• Tristan Charrier
• Arthur Queffelec
• François Schwarzentruber

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 on which the mission needs to be generated and observes the resulting plan being executed.