Scott Kiesel

ICRA Conference 2025 Conference Paper

Reliable and Efficient Multi-Agent Coordination via Graph Neural Network Variational Autoencoders

• Yue Meng
• Nathalie Majcherczyk
• Wenliang Liu
• Scott Kiesel
• Chuchu Fan
• Federico Pecora

Multi-agent coordination is crucial for reliable multi-robot navigation in shared spaces such as automated warehouses. In regions of dense robot traffic, local coordination methods may fail to find a deadlock-free solution. In these scenarios, it is appropriate to let a central unit generate a global schedule that decides the passing order of robots. However, the runtime of such centralized coordination methods increases significantly with the problem scale. In this paper, we propose to leverage Graph Neural Network Variational Autoencoders (GNN-VAE) to solve the multi-agent coordination problem at scale faster than through centralized optimization. We formulate the coordination problem as a graph problem and collect ground truth data using a Mixed-Integer Linear Program (MILP) solver. During training, our learning framework encodes good quality solutions of the graph problem into a latent space. At inference time, solution samples are decoded from the sampled latent variables, and the lowest-cost sample is selected for coordination. By construction, our GNN-VAE framework returns solutions that always respect the constraints of the considered coordination problem. Numerical results show that our approach trained on small-scale problems can achieve high-quality solutions even for large-scale problems with 250 robots, being much faster than other baselines.

AAAI Conference 2021 Conference Paper

Lifelong Multi-Agent Path Finding in Large-Scale Warehouses

• Jiaoyang Li
• Andrew Tinka
• Scott Kiesel
• Joseph W. Durham
• T. K. Satish Kumar
• Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. In this paper, we study the lifelong variant of MAPF, where agents are constantly engaged with new goal locations, such as in large-scale automated warehouses. We propose a new framework Rolling-Horizon Collision Resolution (RHCR) for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of the agents only within a bounded time horizon and ignores collisions beyond it. RHCR is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We empirically evaluate RHCR with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1, 000 agents (= 38. 9% of the empty cells on the map) for simulated warehouse instances, significantly outperforming existing work.

AAMAS Conference 2018 Conference Paper

Conflict-Based Search with Optimal Task Assignment

• Wolfgang H�nig
• Scott Kiesel
• Andrew Tinka
• Joseph W. Durham
• Nora Ayanian

We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based Search (CBS), a framework that has been previously used to find collision-free paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBS-TA, is complete and optimal. The CBS framework allows us to extend our method to ECBS-TA, a bounded suboptimal version. We provide extensive empirical results comparing CBS-TA to task assignment followed by CBS, Conflict-Based Min-Cost-Flow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees.

IROS Conference 2017 Conference Paper

An effort bias for sampling-based motion planning

• Scott Kiesel
• Tianyi Gu 0001
• Wheeler Ruml

Recent advances in sampling-based motion planning have exploited concepts similar to those used in the heuristic graph search community, such as computing heuristic cost-to-go estimates and using state-space abstractions to derive them. Following this trend, we explore how the concept of search effort can be exploited to find plans quickly. Most previous work in motion planning attempts to find plans quickly by preferring states with low cost-to-go. Recent work in graph search suggests that following search effort-to-go estimates can yield faster planning. In this paper, we demonstrate how this idea can be adapted to the context of kinodynamic motion planning. Our planner, BEAST, uses estimates of effort that are learned on-line to guide the expansion of a motion tree toward states through which a plan is estimated to be easy to find. We present results with four different simulated vehicles (car, hovercraft, blimp and quadrotor) in six different environments indicating that BEAST is able to find solutions much more quickly and has a higher success rate than previous methods. We see this work as further strengthening the algorithmic connections between motion planning and heuristic graph search.

JAIR Journal 2015 Journal Article

Achieving Goals Quickly Using Real-time Search: Experimental Results in Video Games

• Scott Kiesel
• Ethan Burns
• Wheeler Ruml

In real-time domains such as video games, planning happens concurrently with execution and the planning algorithm has a strictly bounded amount of time before it must return the next action for the agent to execute. We explore the use of real-time heuristic search in two benchmark domains inspired by video games. Unlike classic benchmarks such as grid pathfinding and the sliding tile puzzle, these new domains feature exogenous change and directed state space graphs. We consider the setting in which planning and acting are concurrent and we use the natural objective of minimizing goal achievement time. Using both the classic benchmarks and the new domains, we investigate several enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is better to plan after each action or to use a dynamically sized lookahead, 2) A*-based lookahead can cause undesirable actions to be selected, and 3) on-line de-biasing of the heuristic can lead to improved performance. We hope this work encourages future research on applying real-time search in dynamic domains.

IJCAI Conference 2015 Conference Paper

Max Is More than Min: Solving Maximization Problems with Heuristic Search

• Roni Stern
• Scott Kiesel
• Rami Puzis
• Ariel Felner
• Wheeler Ruml

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra’s algorithm, weighted A*, and depth-first search.

AAAI Conference 2015 Conference Paper

Non-Classical Planning for Robotic Applications

• Scott Kiesel

AAAI Conference 2015 Conference Paper

Recursive Best-First Search with Bounded Overhead

• Matthew Hatem
• Scott Kiesel
• Wheeler Ruml

There are two major paradigms for linear-space heuristic search: iterative deepening (IDA*) and recursive best-first search (RBFS). While the node regeneration overhead of IDA* is easily characterized in terms of the heuristic branching factor, the overhead of RBFS depends on how widely the promising nodes are separated in the search tree, and is harder to anticipate. In this paper, we present two simple techniques for improving the performance of RBFS while maintaining its advantages over IDA*. While these techniques work well in practice, they do not provide any theoretical bounds on the amount of regeneration overhead. To this end, we introduce RBFSCR, the first method for provably bounding the regeneration overhead of RBFS. We show empirically that this improves its performance in several domains, both for optimal and suboptimal search, and also yields a better linear-space anytime heuristic search. RBFSCR is the first linear space best-first search robust enough to solve a variety of domains with varying operator costs.

SoCS Conference 2015 Conference Paper

Solving the Snake in the Box Problem with Heuristic Search: First Results

• Alon Palombo
• Roni Stern
• Rami Puzis
• Ariel Felner
• Scott Kiesel
• Wheeler Ruml

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n-dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.

SoCS Conference 2014 Conference Paper

Max is More than Min: Solving Maximization Problems with Heuristic Search

• Roni Stern
• Scott Kiesel
• Rami Puzis
• Ariel Felner
• Wheeler Ruml

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding the longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems — optimal, suboptimal, and bounded suboptimal - and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and a discovered close relationships between Dijkstra

SoCS Conference 2013 Conference Paper

Experimental Real-Time Heuristic Search Results in a Video Game

• Ethan Burns
• Scott Kiesel
• Wheeler Ruml

In real-time domains such as video games, a planning algo- rithm has a strictly bounded time before it must return the next action for the agent to execute. We introduce a realistic video game benchmark domain that is useful for evaluating real-time heuristic search algorithms. Unlike previous bench- marks such as grid pathfinding and the sliding tile puzzle, this new domain includes dynamics and induces a directed graph. Using both the previous and new domains, we investigate sev- eral enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is not dif- ficult to outperform A* when optimizing goal achievement time, 2) it is better to plan after each action than to commit to multiple actions or to use a dynamically sized lookahead, 3) A*-based lookahead can cause undesirable actions to be selected, and 4) on-line de-biasing of the heuristic can lead to improved performance. We hope that this new domain and results will stimulate further research on applying real-time search to dynamic real-time domains.

SoCS Conference 2012 Conference Paper

Abstraction-Guided Sampling for Motion Planning

• Scott Kiesel
• Ethan Burns
• Wheeler Ruml

Motion planning in continuous space is a fundamentalrobotics problem that has been approached from many per-spectives. Rapidly-exploring Random Trees (RRTs) usesampling to efficiently traverse the continuous and high-dimensional state space. Heuristic graph search methods uselower bounds on solution cost to focus effort on portions ofthe space that are likely to be traversed by low-cost solutions. In this work, we bring these two ideas together in a tech-nique called f -biasing: we use estimates of solution cost, computed as in heuristic search, to guide sparse sampling, as in RRTs. We see this new technique as strengthening theconnections between motion planning in robotics and combi-natorial search in artificial intelligence.

ICAPS Conference 2012 Conference Paper

Integrating Vehicle Routing and Motion Planning

• Scott Kiesel
• Ethan Burns
• Christopher Makoto Wilt
• Wheeler Ruml

There has been much interest recently in problems that com-bine high-level task planning with low-level motion planning. In this paper, we present a problem of this kind that arises inmulti-vehicle mission planning. It tightly integrates task al-location and scheduling, who will do what when, with pathplanning, how each task will actually be performed. It ex-tends classical vehicle routing in that the cost of executing aset of high-level tasks can vary significantly in time and costaccording to the low-level paths selected. It extends classi-cal motion planning in that each path must minimize costwhile also respecting temporal constraints, including thoseimposed by the agent's other tasks and the tasks assigned toother agents. Furthermore, the problem is a subtask withinan interactive system and therefore must operate within se-vere time constraints. We present an approach to the problembased on a combination of tabu search, linear programming, and heuristic search. We evaluate our planner on represen-tative problem instances and find that its performance meetsthe demanding requirements of our application. These resultsdemonstrate how integrating multiple diverse techniques cansuccessfully solve challenging real-world planning problemsthat are beyond the reach of any single method.