Author name cluster

Pierre Le Bodic

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Flow-Based Task Assignment for Large-Scale Online Multi-Agent Pickup and Delivery

Yue Zhang
Zhe Chen
Daniel Harabor
Pierre Le Bodic
Peter J. Stuckey

We study the online Multi-Agent Pickup and Delivery (MAPD) problem, where a team of agents must repeatedly serve dynamically appearing tasks on a shared map. Existing methods either rely on simple heuristics, which result in poor decisions, or employ complex reasoning, which suffers from limited scalability under real-time constraints. In this work, we focus on the task assignment subproblem and formulate it as a minimum-cost flow over the environment graph. This eliminates the need for pairwise distance computations and allows agents to be simultaneously assigned to tasks and routed toward them. The resulting flow network also supports guide path extraction which accelerates planning under real-time constraints. This approach supports real-time execution and scales to 20, 000 agents and 30, 000 tasks within 1-second planning time, outperforming existing works in terms of computational efficiency, assignment quality and scalability.

PDF

AAAI Conference 2025 Conference Paper

Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities

Yue Zhang
Zhe Chen
Daniel Harabor
Pierre Le Bodic
Peter J. Stuckey

In multi-agent systems, when we account for the possibility of delays during execution, online planning becomes more complicated, as both execution and planning should be able to handle delays when agents are moving. Lifelong Multi-Agent Path Finding (LMAPF) is the problem of (re)planning the collision-free moves of agents to their goals in a shared space, while agents continuously receive new goals. PIE (Planning and Improving while Executing) is a recent approach to LMAPF which concurrently replans later parts of agents' trajectories while execution occurs. However, the execution is assumed to be perfect. Existing approaches either use policy-based methods to quickly coordinate agents every timestep with instant delay feedback, or deploy an execution policy to adjust a solution for delays on the fly. These approaches may introduce large amounts of unnecessary delays to agents due to their planner guarantees or simple delay-handling policies. In this paper, we extend PIE to define a framework for solving the lifelong MAPF problem with execution delays. We instantiate our framework with different execution and replanning strategies, and experimentally evaluate them. Overall, we find that this framework can substantially improve the throughput by up to a factor 3 for lifelong MAPF, compared to approaches that handle delays with simple execution policies.

PDF Details DOI

SoCS Conference 2024 Conference Paper

Optimal Unlabeled Pebble Motion on Trees

Pierre Le Bodic
Edward Lam 0001

Given a tree, a set of pebbles initially stationed at some nodes of the tree and a set of target nodes, the Unlabeled Pebble Motion on Trees problem (UPMT) asks to find a plan to move the pebbles one-at-a-time from the starting nodes to the target nodes along the edges of the tree while minimizing the number of moves. This paper proposes the first optimal algorithm for UPMT that is asymptotically as fast as possible, as it runs in a time linear in the size of the input (the tree) and the size of the output (the optimal plan).

Details

SoCS Conference 2024 Conference Paper

Planning and Exection in Multi-Agent Path Finding: Models and Algorithms (Extended Abstract)

Yue Zhang 0048
Zhe Chen 0016
Daniel Harabor
Pierre Le Bodic
Peter J. Stuckey

In applications of Multi-Agent Path Finding (MAPF), it is often the sum of planning and execution times that needs to be minimised (i. e. , the Goal Achievement Time). Yet current methods seldom optimise for this objective. Optimal algorithms reduce execution time, but may require exponential planning time. Non-optimal algorithms reduce planning time, but at the expense of increased path length. To address these limitations we introduce PIE (Planning and Improving while Executing), a new framework for concurrent planning and execution in MAPF. We first show how PIE for one-shot MAPF improves practical performance compared to sequential planning and execution. We then adapt PIE to Lifelong MAPF, a popular application setting where agents are continuously assigned new goals and where additional decisions are required to ensure feasibility. We examine a variety of different approaches to overcome these challenges and we conduct comparative experiments vs. recently proposed alternatives. Results show that PIE substantially outperforms existing methods for One-shot and Lifelong MAPF.

Details

ICAPS Conference 2024 Conference Paper

Planning and Execution in Multi-Agent Path Finding: Models and Algorithms

Yue Zhang 0048
Zhe Chen 0016
Daniel Harabor
Pierre Le Bodic
Peter J. Stuckey

In applications of Multi-Agent Path Finding (MAPF), it is often the sum of planning and execution times that needs to be minimised (i. e. , the Goal Achievement Time). Yet current methods seldom optimise for this objective. Optimal algorithms reduce execution time, but may require exponential planning time. Non-optimal algorithms reduce planning time, but at the expense of increased path length. To address these limitations we introduce PIE (Planning and Improving while Executing), a new framework for concurrent planning and execution in MAPF. We show how different instantiations of PIE affect practical performance, including initial planning time, action commitment time and concurrent vs. sequential planning and execution. We then adapt PIE to Lifelong MAPF, a popular application setting where agents are continuously assigned new goals and where additional decisions are required to ensure feasibility. We examine a variety of different approaches to overcome these challenges and we conduct comparative experiments vs. recently proposed alternatives. Results show that PIE substantially outperforms existing methods for One-shot and Lifelong MAPF.

Details

SoCS Conference 2023 Conference Paper

Efficient Multi Agent Path Finding with Turn Actions

Yue Zhang 0048
Daniel Harabor
Pierre Le Bodic
Peter J. Stuckey

Current approaches for real-world Multi-Agent Path Finding (MAPF) usually start with a simplified MAPF model and modify the resulting plans so they are kinematically feasible. We investigate one such problem, called MAPF with turn actions MAPF_T, and show that ignoring the kinematic constraints significantly increases solution cost. A first modification of the popular Conflict-Based Search algorithm to MAPF_T yields significantly better plans but comes at the cost of substantial decreases in scalability. We then introduce several techniques that can improve the performance of CBS for MAPF_T, including stronger and generalised versions of existing symmetry-breaking constraints and a novel pruning technique that eliminates redundant branches in the CBS constraint tree. Experimental results on six popular MAPF domains show convincing improvements for CBS success rate and substantial reductions in node expansions and runtime.

Details

SoCS Conference 2022 Conference Paper

Dual Euclidean Shortest Path Search (Extended Abstract)

Ryan Hechenberger
Peter J. Stuckey
Pierre Le Bodic
Daniel Harabor

The Euclidean Shortest Path Problem (ESPP) asks us to find a minimum length path between two points on a 2D plane while avoiding a set of polygonal obstacles. Existing approaches for ESPP, based on Dijkstra or A* search, are primal methods that gradually build up longer and longer valid paths until they reach the target. In this paper we define an alternative algorithm for ESPP which can avoid this problem. Our approach starts from a path that ignores all obstacles, and generates longer and longer paths, each avoiding more obstacles, until eventually the search finds an optimal valid path.

Details

AAAI Conference 2021 Conference Paper

f-Aware Conflict Prioritization & Improved Heuristics For Conflict-Based Search

Eli Boyarski
Ariel Felner
Pierre Le Bodic
Daniel D. Harabor
Peter J. Stuckey
Sven Koenig

Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF). The main step of CBS is to expand nodes by resolving conflicts (where two agents collide). Choosing the ‘right’ conflict to resolve can greatly speed up the search. CBS first resolves conflicts where the costs (g-values) of the resulting child nodes are larger than the cost of the node to be split. However, the recent addition of high-level heuristics to CBS and expanding nodes according to f = g + h reduces the relevance of this conflict prioritization method. Therefore, we introduce an expanded categorization of conflicts, which first resolves conflicts where the f-values of the child nodes are larger than the f-value of the node to be split, and present a method for identifying such conflicts. We also enhance all known heuristics for CBS by using information about the cost of resolving certain conflicts with only a small computational overhead. Finally, we experimentally demonstrate that both the expanded categorization of conflicts and the improved heuristics contribute to making CBS even more efficient.

PDF Details

SoCS Conference 2021 Conference Paper

Further Improved Heuristics For Conflict-Based Search

Eli Boyarski
Ariel Felner
Pierre Le Bodic
Daniel Harabor
Peter J. Stuckey
Sven Koenig

Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF). At its high level, CBS expands nodes by resolving conflicts. In recent years, admissible heuristics were added to the high level of CBS. We enhance all known heuristic functions for CBS by using information about the cost of resolving certain conflicts, with only a small computational overhead. We experimentally demonstrate that the improved heuristics contribute to making CBS even more efficient.

Details

JAIR Journal 2021 Journal Article

Learning Optimal Decision Sets and Lists with SAT

Jinqiang Yu
Alexey Ignatiev
Peter J. Stuckey
Pierre Le Bodic

Decision sets and decision lists are two of the most easily explainable machine learning models. Given the renewed emphasis on explainable machine learning decisions, both of these machine learning models are becoming increasingly attractive, as they combine small size and clear explainability. In this paper, we define size as the total number of literals in the SAT encoding of these rule-based models as opposed to earlier work that concentrates on the number of rules. In this paper, we develop approaches to computing minimum-size “perfect” decision sets and decision lists, which are perfectly accurate on the training data, and minimal in size, making use of modern SAT solving technology. We also provide a new method for determining optimal sparse alternatives, which trade off size and accuracy. The experiments in this paper demonstrate that the optimal decision sets computed by the SAT-based approach are comparable with the best heuristic methods, but much more succinct, and thus, more explainable. We contrast the size and test accuracy of optimal decisions lists versus optimal decision sets, as well as other state-of-the-art methods for determining optimal decision lists. Finally, we examine the size of average explanations generated by decision sets and decision lists.

PDF Details DOI

SoCS Conference 2021 Conference Paper

Multi-Target Search in Euclidean Space with Ray Shooting

Ryan Hechenberger
Daniel Harabor
Muhammad Aamir Cheema
Peter J. Stuckey
Pierre Le Bodic

The shortest path problem (SPP) asks us to find a minimum length path between two points, usually on a graph. In a Euclidean environment the points are in a 2D plane and here the path must avoid a set of polygonal obstacles. Solution methods for this Euclidean SPP (ESPP) typically convert the continuous 2D map into a discretised representation, like a graph or navigation mesh. RayScan is a recent and fast ESPP algorithm which avoids the preprocessing step by using a combination of "ray shooting" and polygon scanning. In this paper we improve the performance of RayScan using spatial reasoning and ray caching techniques. We also extend the algorithm, from single-target search to a multi-target setting. Comparative game map experiments show a substantial speedup.

Details

TCS Journal 2020 Journal Article

Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth

Cédric Bentz
Pierre Le Bodic

In the Multicut problem, the input consists of a graph and a set of pairs of terminal vertices that have to be disconnected by the removal of a set of edges with minimum total weight. The Partial Multicut problem generalizes Multicut by only requiring a given number of pairs of terminals to be disconnected by the removal of edges. It has been shown that Multicut remains APX-hard if the treewidth t w ( G ) of its input graph G is bounded, but that it is FPT w. r. t. t w ( G + H ), where H is the demand graph, whose vertices are the terminals and whose edges are the pairs of terminals. We prove that this also holds for Partial Multicut. Furthermore, it has been proved that Multicut also becomes polynomial-time solvable if t w ( G ) is bounded and H is complete (this is the Multiterminal Cut problem). We extend this result in two directions, by proving that Multicut remains polynomial-time solvable if t w ( G + H ¯ ) is bounded, and that this remains true for Partial Multicut. Finally, we show that if we further generalize the problem to allow non-unitary profits for pairs of terminals, then the problem is weakly NP-hard and has an FPTAS if t w ( G + H ) is bounded, and becomes APX-hard if t w ( G + H ¯ ) is bounded.

Details DOI

SoCS Conference 2020 Conference Paper

F-Cardinal Conflicts in Conflict-Based Search

Eli Boyarski
Daniel Harabor
Peter J. Stuckey
Pierre Le Bodic
Ariel Felner

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF) which features strong performance. In CBS, one conflict in a high-level node is resolved to generate two child nodes, until a node with no conflicts is found. Choosing the right conflict to resolve can greatly speed up the search. It is currently recommended to resolve cardinal conflicts first, resolving them yields two child nodes with a higher cost than the cost of their parent. However, since the recent addition of high-level heuristics to CBS, when resolving cardinal conflicts, the h-value of high-level child nodes often decreases by the same amount as their cost increases. This diminishes the effectiveness of the cardinal conflicts distinction. We propose an expanded categorization of conflicts into f-cardinal, g-cardinal, and non-cardinal. F-cardinal conflicts should be resolved first. Resolving f-cardinal conflicts generates child nodes with an increased f-value relative to their parent. We propose two methods for identifying f-cardinal conflicts. Finally, we demonstrate on standard benchmarks that choosing conflicts according to this expanded categorization increases the effectiveness of modern CBS.

Details

ICAPS Conference 2020 Conference Paper

New Valid Inequalities in Branch-and-Cut-and-Price for Multi-Agent Path Finding

Edward Lam 0001
Pierre Le Bodic

BCP, a state-of-the-art algorithm for optimal Multi-agent Path Finding, uses the branch-and-cut-and-price framework to decompose the problem into (1) a master problem that selects a set of collision-free low-cost paths, (2) a pricing problem that adds lower-cost paths to the master problem, (3) separation problems that resolve various kinds of conflicts in the master problem, and (4) branching rules that split the nodes in the high-level branch-and-bound search tree. This paper focuses on the separation aspects of the decomposition by introducing five new classes of fractional conflicts and valid inequalities that remove these conflicts to tighten the linear programming relaxation in the master problem. Experimental results on 12820 instances across 16 maps indicate that including the five families of inequalities allows BCP to solve an additional 585 instances, optimize the same instances 41% faster, and solve 2068 more instances than CBSH-RM and 157 more than Lazy CBS.

Details

ICAPS Conference 2020 Conference Paper

Online Computation of Euclidean Shortest Paths in Two Dimensions

Ryan Hechenberger
Peter J. Stuckey
Daniel Harabor
Pierre Le Bodic
Muhammad Aamir Cheema

We consider the online version of Euclidean Shortest Path (ESP): a problem that asks for distance minimal trajectories between traversable pairs of points in the plane. The problem is made challenging because each trajectory must avoid a set of non-traversable obstacles represented as polygons. To solve ESP practitioners will often preprocess the environment and construct specialised data structures, such as visibility graphs and navigation meshes. Pathfinding queries on these data structures are fast but the preprocessed data becomes invalidated when obstacles move or change. In this work we propose RayScan, a new algorithmic approach for ESP which is entirely online. The central idea is simple: each time we expand a node we also cast a ray toward the target. If an obstacle intersects the ray we scan its perimeter for a turning point; i. e. a vertex from which a new ray can continue unimpeded towards the target. RayScan is fast, optimal and entirely online. Experiments show that it can significantly improve upon current state-of-the-art methods for ESP in cases where the set of obstacles is dynamic.

Details

IJCAI Conference 2019 Conference Paper

Branch-and-Cut-and-Price for Multi-Agent Pathfinding

Edward Lam
Pierre Le Bodic
Daniel D. Harabor
Peter J. Stuckey

There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches using Branch-and-Cut-and-Price, a decomposition framework developed for mathematical optimization. We formalize BCP and compare it empirically against CBSH and CBSH-RM, two leading search-based solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the state-of-the-art: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps.

PDF Details

AAAI Conference 2019 Conference Paper

Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation

Daniel Anderson
Gregor Hendel
Pierre Le Bodic
Merlin Viernickel

We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed- Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.

PDF Details

IJCAI Conference 2017 Conference Paper

Estimating the size of search trees by sampling with domain knowledge

Gleb Belov
Samuel Esler
Dylan Fernando
Pierre Le Bodic
George L. Nemhauser

We show how recently-defined abstract models of the Branch-and-Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.

PDF Details

AAAI Conference 2016 Conference Paper

Learning to Branch in Mixed Integer Programming

Elias Khalil
Pierre Le Bodic
Le Song
George Nemhauser
Bistra Dilkina

The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and ofﬂine experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP. Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-evaluate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-speciﬁc, and is performed on-the-ﬂy while executing a branch-and-bound search to solve the instance. Experiments on benchmark instances indicate that our method produces signiﬁcantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.

PDF Details