Publications | Rishi Veerapaneni

This list of publications is periodically updated, see my google scholar for a more up-to-date list!

2025

Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks

Rishi Veerapaneni, Alvin Tang*, Haodong He*, Sophia Zhao*, Viraj Shah*, Yidai Cen*, Ziteng Ji*, Gabriel Olin, Jon Arrizabalaga, Yorai Shaoul, and 2 more authors

arXiv preprint arxiv:2510.00425, 2025

Abs arXiv Bib Website

Imagine the future construction site, hospital, office, or even sophisticated household with dozens of robots bought from different manufacturers. How can we enable these different systems to effectively move in a shared environment, given that each robot may have its own independent motion planning system? This work shows how we can get efficient collision-free movements between algorithmically heterogeneous agents by using Conflict-Based Search (Sharon et al. 2015) as a protocol. At its core, the CBS Protocol requires one specific single-agent motion planning API; finding a collision-free path that satisfies certain space-time constraints. Given such an API, CBS uses a central planner to find collision-free paths - independent of how the API is implemented. We show how this protocol enables multi-agent motion planning for a heterogeneous team of agents completing independent tasks with a variety of single-agent planners including: Heuristic Search (e.g., A*), Sampling Based Search (e.g., RRT), Optimization (e.g., Direct Collocation), Diffusion, and Reinforcement Learning.
@article{veerapaneni2025cbs_protocol, title = {Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks}, author = {Veerapaneni, Rishi and Tang, Alvin and He, Haodong and Zhao, Sophia and Shah, Viraj and Cen, Yidai and Ji, Ziteng and Olin, Gabriel and Arrizabalaga, Jon and Shaoul, Yorai and Li, Jiaoyang and Likhachev, Maxim}, year = {2025}, journal = {arXiv preprint arxiv:2510.00425}, archiveprefix = {arXiv}, primaryclass = {cs.MA}, }
Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees

Tiannan Zhang, Rishi Veerapaneni, Shao-Hung Chan, Jiaoyang Li, and Maxim Likhachev

arXiv preprint arxiv:2509.15381, 2025

Abs arXiv Bib

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for a team of agents. Although several MAPF methods which solve full-horizon MAPF have completeness guarantees, very few MAPF methods that plan partial paths have completeness guarantees. Recent work introduced the Windowed Complete MAPF (WinC-MAPF) framework, which shows how windowed optimal MAPF solvers (e.g., SS-CBS) can use heuristic updates and disjoint agent groups to maintain completeness even when planning partial paths (Veerapaneni et al. 2024). A core limitation of WinC-MAPF is that they required optimal MAPF solvers. Our main contribution is to extend WinC-MAPF by showing how we can use a bounded suboptimal solver while maintaining completeness. In particular, we design Dynamic Agent Grouping ECBS (DAG-ECBS) which dynamically creates and plans agent groups while maintaining that each agent group solution is bounded suboptimal. We prove how DAG-ECBS can maintain completeness in the WinC-MAPF framework. DAG-ECBS shows improved scalability compared to SS-CBS and can outperform windowed ECBS without completeness guarantees. More broadly, our work serves as a blueprint for designing more MAPF methods that can use the WinC-MAPF framework.
@article{zhang2025dag_ecbs, title = {Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees}, author = {Zhang, Tiannan and Veerapaneni, Rishi and Chan, Shao-Hung and Li, Jiaoyang and Likhachev, Maxim}, year = {2025}, journal = {arXiv preprint arxiv:2509.15381}, archiveprefix = {arXiv}, primaryclass = {cs.MA}, }
BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs

Yifan Su, Rishi Veerapaneni, and Jiaoyang Li

arXiv preprint arxiv:2508.04849, 2025

Abs arXiv Bib

Multi-Agent Path Finding (MAPF) requires computing collision-free paths for multiple agents in shared environment. Most MAPF planners assume that each agent reaches a specific location at a specific timestep, but this is infeasible to directly follow on real systems where delays often occur. To address collisions caused by agents deviating due to delays, the Temporal Plan Graph (TPG) was proposed, which converts a MAPF time dependent solution into a time independent set of inter-agent dependencies. Recently, a Bidirectional TPG (BTPG) was proposed which relaxed some dependencies into “bidirectional pairs" and improved efficiency of agents executing their MAPF solution with delays. Our work improves upon this prior work by designing an algorithm, BPTG-max, that finds more bidirectional pairs. Our main theoretical contribution is in designing the BTPG-max algorithm is locally optimal, i.e. which constructs a BTPG where no additional bidirectional pairs can be added. We also show how in practice BTPG-max leads to BTPGs with significantly more bidirectional edges, superior anytime behavior, and improves robustness to delays.
@article{su2025btpg-max, title = {BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs}, author = {Su, Yifan and Veerapaneni, Rishi and Li, Jiaoyang}, year = {2025}, journal = {arXiv preprint arxiv:2508.04849}, archiveprefix = {arXiv}, primaryclass = {cs.MA}, }
Real-Time LaCAM for Real-Time MAPF

Runzhe Liang*, Rishi Veerapaneni*, Daniel Harabor, Jiaoyang Li, and Maxim Likhachev

In Proceedings of the International Symposium on Combinatorial Search (SoCS), 2025

Abs arXiv Bib PDF Code

The vast majority of Multi-Agent Path Finding (MAPF) methods with completeness guarantees require planning full-horizon paths. However, planning full-horizon paths can take too long and be impractical in real-world applications. Instead, real-time planning and execution, which only allows the planner a finite amount of time before executing and replanning, is more practical for real-world multi-agent systems. Several methods utilize real-time planning schemes but none are provably complete, which leads to livelock or deadlock. Our main contribution is Real-Time LaCAM, the first Real-Time MAPF method with provable completeness guarantees. We do this by leveraging LaCAM (Okumura 2023) in an incremental fashion. Our results show how we can iteratively plan for congested environments with a cutoff time of milliseconds while still maintaining the same success rate as full-horizon LaCAM. We also show how it can be used with a single-step learned MAPF policy.
@inproceedings{liang2025real_time_lacam, title = {Real-Time LaCAM for Real-Time MAPF}, author = {Liang, Runzhe and Veerapaneni, Rishi and Harabor, Daniel and Li, Jiaoyang and Likhachev, Maxim}, booktitle = {Proceedings of the International Symposium on Combinatorial Search (SoCS)}, volume = {18}, pages = {196-200}, year = {2025}, doi = {10.1609/socs.v18i1.35993}, url = {https://ojs.aaai.org/index.php/SOCS/article/view/35993}, }
Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions

Muhammad Suhail Saleem, Rishi Veerapaneni, and Maxim Likhachev

In Proceedings of the International Symposium on Combinatorial Search (SoCS), 2025

Abs arXiv Bib PDF

Heuristic search solvers like RTDP-Bel and LAO* have proven effective for computing optimal and bounded sub-optimal solutions for Partially Observable Markov Decision Processes (POMDPs), which are typically formulated as belief MDPs. A belief represents a probability distribution over possible system states. Given a parent belief and an action, computing belief state transitions involves Bayesian updates that combine the transition and observation models of the POMDP to determine successor beliefs and their transition probabilities. However, there is a class of problems, specifically in robotics, where computing these transitions can be prohibitively expensive due to costly physics simulations, raycasting, or expensive collision checks required by the underlying transition and observation models, leading to long planning times. To address this challenge, we propose Lazy RTDP-Bel and Lazy LAO*, which defer computing expensive belief state transitions by leveraging Q-value estimation, significantly reducing planning time. These algorithms are specific instantiations of the broader idea of lazy search for POMDPs. We demonstrate the superior performance of the proposed lazy planners in domains such as contact-rich manipulation for pose estimation, outdoor navigation in rough terrain, and indoor navigation with a 1-D Lidar sensor. Additionally, we discuss practical Q-value estimation techniques for commonly encountered problem classes that our lazy planners can leverage. Our results show that lazy heuristic search methods dramatically improve planning speed by postponing expensive belief transition evaluations while maintaining solution quality.
@inproceedings{saleem2025lazy_pomdp, title = {Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions}, author = {Saleem, Muhammad Suhail and Veerapaneni, Rishi and Likhachev, Maxim}, booktitle = {Proceedings of the International Symposium on Combinatorial Search (SoCS)}, volume = {18}, pages = {118-126}, year = {2025}, doi = {10.1609/socs.v18i1.35983}, url = {https://ojs.aaai.org/index.php/SOCS/article/view/35983}, }
Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding

He Jiang*, Yutong Wang*, Rishi Veerapaneni, Tanishq Duhan, Guillaume Sartoretti, and Jiaoyang Li

In 2025 IEEE International Conference on Robotics and Automation (ICRA), 2025

Abs arXiv Bib PDF

Best Student and Best Multi-Agent Systems Paper ⭐

Lifelong Multi-Agent Path Finding (LMAPF) is a variant of MAPF where agents are continually assigned new goals, necessitating frequent re-planning to accommodate these dynamic changes. Recently, this field has embraced learning-based methods, which reactively generate single-step actions based on individual local observations. However, it is still challenging for them to match the performance of the best search-based algorithms, especially in large-scale settings. This work proposes an imitation-learning-based LMAPF solver that introduces a novel communication module and systematic single-step collision resolution and global guidance techniques. Our proposed solver, Scalable Imitation Learning for LMAPF (SILLM), inherits the fast reasoning speed of learning-based methods and the high solution quality of search-based methods with the help of modern GPUs. Across six large-scale maps with up to 10,000 agents and varying obstacle structures, SILLM surpasses the best learning- and search-based baselines, achieving average throughput improvements of 137.7% and 16.0%, respectively. Furthermore, SILLM also beats the winning solution of the 2023 League of Robot Runners, an international LMAPF competition sponsored by Amazon Robotics. Finally, we validated SILLM with 10 real robots and 100 virtual robots in a mockup warehouse environment.
@inproceedings{jiang2025scalable_il_lmapf, author = {Jiang, He and Wang, Yutong and Veerapaneni, Rishi and Duhan, Tanishq and Sartoretti, Guillaume and Li, Jiaoyang}, booktitle = {2025 IEEE International Conference on Robotics and Automation (ICRA)}, title = {Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding}, year = {2025}, pages = {1-7}, doi = {10.1109/ICRA55743.2025.11127445}, }
Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large-Scale Imitation Learning for MAPF

Rishi Veerapaneni*, Arthur Jakobsson*, Kevin Ren, Samuel Kim, Jiaoyang Li, and Maxim Likhachev

In 2025 IEEE International Conference on Robotics and Automation (ICRA), 2025

Abs arXiv Bib PDF Code Website

Multi-Agent Path Finding (MAPF) is the problem of effectively finding efficient collision-free paths for a group of agents in a shared workspace. The MAPF community has largely focused on developing high-performance heuristic search methods. Recently, several works have applied various machine learning (ML) techniques to solve MAPF, usually involving sophisticated architectures, reinforcement learning techniques, and set-ups, but none using large amounts of high-quality supervised data. Our initial objective in this work was to show how simple large scale imitation learning of high-quality heuristic search methods can lead to state-of-the-art ML MAPF performance. However, we find that, at least with our model architecture, simple large scale (700k examples with hundreds of agents per example) imitation learning does \textitnot produce impressive results. Instead, we find that by using prior work that post-processes MAPF model predictions to resolve 1-step collisions (CS-PIBT), we can train a simple ML MAPF model in minutes that dramatically outperforms existing ML MAPF policies. This has serious implications for all future ML MAPF policies (with local communication) which currently struggle to scale. In particular, this finding implies that future learnt policies should (1) always use smart 1-step collision shields (e.g. CS-PIBT), (2) always include the collision shield with greedy actions as a baseline (e.g. PIBT) and (3) motivates future models to focus on longer horizon / more complex planning as 1-step collisions can be efficiently resolved.
@inproceedings{veerapaneni2025work_smart_not_harder, author = {Veerapaneni, Rishi and Jakobsson, Arthur and Ren, Kevin and Kim, Samuel and Li, Jiaoyang and Likhachev, Maxim}, booktitle = {2025 IEEE International Conference on Robotics and Automation (ICRA)}, title = {Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large-Scale Imitation Learning for MAPF}, year = {2025}, pages = {10229-10236}, doi = {10.1109/ICRA55743.2025.11128836}, }
Windowed MAPF with Completeness Guarantees

Rishi Veerapaneni, Muhammad Suhail Saleem, Jiaoyang Li, and Maxim Likhachev

Proceedings of the AAAI Conference on Artificial Intelligence, 2025

Abs arXiv Bib PDF

Traditional multi-agent path finding (MAPF) methods try to compute entire collision free start-goal paths, with several algorithms offering completeness guarantees. However, computing partial paths offers significant advantages including faster planning, adaptability to changes, and enabling decentralized planning. Methods that compute partial paths employ a "windowed" approach and only try to find collision free paths for a limited timestep horizon. While this improves flexibility, this adaptation introduces incompleteness; all existing windowed approaches can become stuck in deadlock or livelock. Our main contribution is to introduce our framework, WinC-MAPF, for Windowed MAPF that enables completeness. Our framework leverages heuristic update insights from single-agent real-time heuristic search algorithms and agent independence ideas from MAPF algorithms. We also develop Single-Step Conflict Based Search (SS-CBS), an instantiation of this framework using a novel modification to CBS. We show how SS-CBS, which only plans a single step and updates heuristics, can effectively solve tough scenarios where existing windowed approaches fail.
@article{veerapaneni2025winc_mapf, author = {Veerapaneni, Rishi and Saleem, Muhammad Suhail and Li, Jiaoyang and Likhachev, Maxim}, title = {Windowed MAPF with Completeness Guarantees}, volume = {39}, url = {https://ojs.aaai.org/index.php/AAAI/article/view/34499}, doi = {10.1609/aaai.v39i22.34499}, number = {22}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, year = {2025}, pages = {23323-23332}, }
Anytime Single-Step MAPF Planning with Anytime PIBT

Nayesha Gandotra*, Rishi Veerapaneni*, Muhammad Suhail Saleem, Daniel Harabor, Jiaoyang Li, and Maxim Likhachev

arXiv preprint arxiv:2504.07841, 2025

Abs arXiv Bib

PIBT is a popular Multi-Agent Path Finding (MAPF) method at the core of many state-of-the-art MAPF methods including LaCAM, CS-PIBT, and WPPL. The main utility of PIBT is that it is a very fast and effective single-step MAPF solver and can return a collision-free single-step solution for hundreds of agents in less than a millisecond. However, the main drawback of PIBT is that it is extremely greedy in respect to its priorities and thus leads to poor solution quality. Additionally, PIBT cannot use all the planning time that might be available to it and returns the first solution it finds. We thus develop Anytime PIBT, which quickly finds a one-step solution identically to PIBT but then continuously improves the solution in an anytime manner. We prove that Anytime PIBT converges to the optimal solution given sufficient time. We experimentally validate that Anytime PIBT can rapidly improve single-step solution quality within milliseconds and even find the optimal single-step action. However, we interestingly find that improving the single-step solution quality does not have a significant effect on full-horizon solution costs.
@article{gandotra2025anytime_pibt, title = {Anytime Single-Step MAPF Planning with Anytime PIBT}, author = {Gandotra, Nayesha and Veerapaneni, Rishi and Saleem, Muhammad Suhail and Harabor, Daniel and Li, Jiaoyang and Likhachev, Maxim}, year = {2025}, journal = {arXiv preprint arxiv:2504.07841}, archiveprefix = {arXiv}, primaryclass = {cs.AI}, }

2024

ANAVI: Audio Noise Awareness using Visuals of Indoor environments for NAVIgation

Vidhi Jain, Rishi Veerapaneni, and Yonatan Bisk

8th Annual Conference on Robot Learning (CoRL), 2024

Abs arXiv Bib PDF Website

We propose Audio Noise Awareness using Visuals of Indoors for NAVIgation for quieter robot path planning. While humans are naturally aware of the noise they make and its impact on those around them, robots currently lack this awareness. A key challenge in achieving audio awareness for robots is estimating how loud will the robot’s actions be at a listener’s location? Since sound depends upon the geometry and material composition of rooms, we train the robot to passively perceive loudness using visual observations of indoor environments. To this end, we generate data on how loud an ’impulse’ sounds at different listener locations in simulated homes, and train our Acoustic Noise Predictor (ANP). Next, we collect acoustic profiles corresponding to different actions for navigation. Unifying ANP with action acoustics, we demonstrate experiments with wheeled (Hello Robot Stretch) and legged (Unitree Go2) robots so that these robots adhere to the noise constraints of the environment.
@article{jain2024anavi, title = {ANAVI: Audio Noise Awareness using Visuals of Indoor environments for NAVIgation}, author = {Jain, Vidhi and Veerapaneni, Rishi and Bisk, Yonatan}, year = {2024}, journal = {8th Annual Conference on Robot Learning (CoRL)}, }
A POMDP-based hierarchical planning framework for manipulation under pose uncertainty

Muhammad Suhail Saleem, Rishi Veerapaneni, and Maxim Likhachev

arXiv preprint arxiv:2409.18775, 2024

Abs arXiv Bib

Robots often face challenges in domestic environments where visual feedback is ineffective, such as retrieving objects obstructed by occlusions or finding a light switch in the dark. In these cases, utilizing contacts to localize the target object can be effective. We propose an online planning framework using binary contact signals for manipulation tasks with pose uncertainty, formulated as a Partially Observable Markov Decision Process (POMDP). Naively representing the belief as a particle set makes planning infeasible due to the large uncertainties in domestic settings, as identifying the best sequence of actions requires rolling out thousands of actions across millions of particles, taking significant compute time. To address this, we propose a hierarchical belief representation. Initially, we represent the uncertainty coarsely in a 3D volumetric space. Policies that refine uncertainty in this space are computed and executed, and once uncertainty is sufficiently reduced, the problem is translated back into the particle space for further refinement before task completion. We utilize a closed-loop planning and execution framework with a heuristic-search-based anytime solver that computes partial policies within a limited time budget. The performance of the framework is demonstrated both in real world and in simulation on the high-precision task of inserting a plug into a port using a UR10e manipulator, resolving positional uncertainties up to 50 centimeters and angular uncertainties close to 2π. Experimental results highlight the framework’s effectiveness, achieving a 93% success rate in the real world and over 50% improvement in solution quality compared to greedy baselines, significantly accelerating planning and enabling real-time solutions for complex problems.
@article{saleem2024manipulation_pose_uncertainty, title = {A POMDP-based hierarchical planning framework for manipulation under pose uncertainty}, author = {Saleem, Muhammad Suhail and Veerapaneni, Rishi and Likhachev, Maxim}, year = {2024}, journal = {arXiv preprint arxiv:2409.18775}, archiveprefix = {arXiv}, primaryclass = {cs.RO}, }
Unconstraining Multi-Robot Manipulation: Enabling Arbitrary Constraints in ECBS with Bounded Sub-Optimality

Yorai Shaoul*, Rishi Veerapaneni*, Maxim Likhachev, and Jiaoyang Li

In Proceedings of the International Symposium on Combinatorial Search (SoCS), 2024

Abs arXiv Bib PDF

Multi-Robot-Arm Motion Planning (M-RAMP) is a challenging problem featuring complex single-agent planning and multi-agent coordination. Recent advancements in extending the popular Conflict-Based Search (CBS) algorithm have made large strides in solving Multi-Agent Path Finding (MAPF) problems. However, fundamental challenges remain in applying CBS to M-RAMP. A core challenge is the existing reliance of the CBS framework on conservative "complete" constraints. These constraints ensure solution guarantees but often result in slow pruning of the search space – causing repeated expensive single-agent planning calls. Therefore, even though it is possible to leverage domain knowledge and design incomplete M-RAMP-specific CBS constraints to more efficiently prune the search, using these constraints would render the algorithm itself incomplete. This forces practitioners to choose between efficiency and completeness. In light of these challenges, we propose a novel algorithm, Generalized ECBS, aimed at removing the burden of choice between completeness and efficiency in MAPF algorithms. Our approach enables the use of arbitrary constraints in conflict-based algorithms while preserving completeness and bounding sub-optimality. This enables practitioners to capitalize on the benefits of arbitrary constraints and opens a new space for constraint design in MAPF that has not been explored. We provide a theoretical analysis of our algorithms, propose new "incomplete" constraints, and demonstrate their effectiveness through experiments in M-RAMP.
@inproceedings{shaoul2024generalized_ecbs, title = {Unconstraining Multi-Robot Manipulation: Enabling Arbitrary Constraints in ECBS with Bounded Sub-Optimality}, author = {Shaoul, Yorai and Veerapaneni, Rishi and Likhachev, Maxim and Li, Jiaoyang}, booktitle = {Proceedings of the International Symposium on Combinatorial Search (SoCS)}, volume = {17}, pages = {109-117}, year = {2024}, doi = {10.1609/socs.v17i1.31548}, url = {https://ojs.aaai.org/index.php/SOCS/article/view/31548}, }
Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities

He Jiang, Yulun Zhang, Rishi Veerapaneni, and Jiaoyang Li

In Proceedings of the International Symposium on Combinatorial Search (SoCS), 2024

Abs arXiv Bib PDF

Multi-Agent Path Finding (MAPF) is the problem of moving multiple agents from starts to goals without collisions. Lifelong MAPF (LMAPF) extends MAPF by continuously assigning new goals to agents. We present our winning approach to the 2023 League of Robot Runners LMAPF competition, which leads us to several interesting research challenges and future directions. In this paper, we outline three main research challenges. The first challenge is to search for high-quality LMAPF solutions within a limited planning time (e.g., 1s per step) for a large number of agents (e.g., 10,000) or extremely high agent density (e.g., 97.7%). We present future directions such as developing more competitive rule-based and anytime MAPF algorithms and parallelizing state-of-the-art MAPF algorithms. The second challenge is to alleviate congestion and the effect of myopic behaviors in LMAPF algorithms. We present future directions, such as developing moving guidance and traffic rules to reduce congestion, incorporating future prediction and real-time search, and determining the optimal agent number. The third challenge is to bridge the gaps between the LMAPF models used in the literature and real-world applications. We present future directions, such as dealing with more realistic kinodynamic models, execution uncertainty, and evolving systems.
@inproceedings{jiang2024scaling_lifelong_mapf, title = {Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities}, author = {Jiang, He and Zhang, Yulun and Veerapaneni, Rishi and Li, Jiaoyang}, booktitle = {Proceedings of the International Symposium on Combinatorial Search (SoCS)}, volume = {17}, pages = {234-242}, year = {2024}, doi = {10.1609/socs.v17i1.31565}, url = {https://ojs.aaai.org/index.php/SOCS/article/view/31565}, }
From Space-Time to Space-Order: Directly Planning a Temporal Planning Graph by Redefining CBS

Yu Wu, Rishi Veerapaneni, Jiaoyang Li, and Maxim Likhachev

arXiv preprint arxiv:2404.15137, 2024

Abs arXiv Bib

The majority of multi-agent path finding (MAPF) methods compute collision-free space-time paths which require agents to be at a specific location at a specific discretized timestep. However, executing these space-time paths directly on robotic systems is infeasible due to real-time execution differences (e.g. delays) which can lead to collisions. To combat this, current methods translate the space-time paths into a temporal plan graph (TPG) that only requires that agents observe the order in which they navigate through locations where their paths cross. However, planning space-time paths and then post-processing them into a TPG does not reduce the required agent-to-agent coordination, which is fixed once the space-time paths are computed. To that end, we propose a novel algorithm Space-Order CBS that can directly plan a TPG and explicitly minimize coordination. Our main theoretical insight is our novel perspective on viewing a TPG as a set of space-visitation order paths where agents visit locations in relative orders (e.g. 1st vs 2nd) as opposed to specific timesteps. We redefine unique conflicts and constraints for adapting CBS for space-order planning. We experimentally validate how Space-Order CBS can return TPGs which significantly reduce coordination, thus subsequently reducing the amount of agent-agent communication and leading to more robustness to delays during execution.
@article{wu2024space_order_cbs, title = {From Space-Time to Space-Order: Directly Planning a Temporal Planning Graph by Redefining CBS}, author = {Wu, Yu and Veerapaneni, Rishi and Li, Jiaoyang and Likhachev, Maxim}, year = {2024}, journal = {arXiv preprint arxiv:2404.15137}, archiveprefix = {arXiv}, primaryclass = {cs.MA}, }
A Data Efficient Framework for Learning Local Heuristics

Rishi Veerapaneni*, Jonathan Park*, Muhammad Suhail Saleem, and Maxim Likhachev

In Proceedings of the International Symposium on Combinatorial Search (SoCS), 2024

Abs arXiv Bib PDF

With the advent of machine learning, there have been several recent attempts to learn effective and generalizable heuristics. Local Heuristic A* (LoHA*) is one recent method that instead of learning the entire heuristic estimate, learns a "local" residual heuristic that estimates the cost to escape a region (Veerapaneni et al 2023). LoHA*, like other supervised learning methods, collects a dataset of target values by querying an oracle on many planning problems (in this case, local planning problems). This data collection process can become slow as the size of the local region increases or if the domain requires expensive collision checks. Our main insight is that when an A* search solves a start-goal planning problem it inherently ends up solving multiple local planning problems. We exploit this observation to propose an efficient data collection framework that does <1/10th the amount of work (measured by expansions) to collect the same amount of data in comparison to baselines. This idea also enables us to run LoHA* in an online manner where we can iteratively collect data and improve our model while solving relevant start-goal tasks. We demonstrate the performance of our data collection and online framework on a 4D (x,y,θ,v) navigation domain.
@inproceedings{veerapaneni2024data_efficient_local_heuristics, title = {A Data Efficient Framework for Learning Local Heuristics}, author = {Veerapaneni, Rishi and Park, Jonathan and Saleem, Muhammad Suhail and Likhachev, Maxim}, doi = {10.1609/socs.v17i1.31563}, booktitle = {Proceedings of the International Symposium on Combinatorial Search (SoCS)}, volume = {17}, pages = {223-227}, year = {2024}, url = {https://ojs.aaai.org/index.php/SOCS/article/view/31563}, }
MAPF in 3D Warehouses: Dataset and Analysis

Qian Wang*, Rishi Veerapaneni*, Yu Wu, Jiaoyang Li, and Maxim Likhachev

International Conference on Automated Planning and Scheduling (ICAPS), 2024

Abs Bib PDF Website

Recent works have made significant progress in multi-agent path finding (MAPF), with modern methods being able to scale to hundreds of agents, handle unexpected delays, work in groups, etc. The vast majority of these methods have focused on 2D "grid world" domains. However, modern warehouses often utilize multi-agent robotic systems that can move in 3D, enabling dense storage but resulting in a more complex multi-agent planning problem. Motivated by this, we introduce and experimentally analyze the application of MAPF to 3D warehouse management, and release the first (see http://mapf.info/index.php/Main/Benchmarks) open-source 3D MAPF dataset. We benchmark two state-of-the-art MAPF methods, EECBS and MAPF-LNS2, and show how different hyper-parameters affect these methods across various 3D MAPF problems. We also investigate how the warehouse structure itself affects MAPF performance. Based on our experimental analysis, we find that a fast low-level search is critical for 3D MAPF, EECBS’s suboptimality significantly changes the effect of certain CBS techniques, and certain warehouse designs can noticeably influence MAPF scalability and speed. An additional important observation is that, overall, the tested 2D MAPF techniques scaled well to 3D warehouses and demonstrate how the MAPF community’s progress in 2D can generalize to 3D warehouses.
@article{wang2024mapf_3d_warehouse, title = {MAPF in 3D Warehouses: Dataset and Analysis}, volume = {34}, url = {https://ojs.aaai.org/index.php/ICAPS/article/view/31525}, doi = {10.1609/icaps.v34i1.31525}, number = {1}, journal = {International Conference on Automated Planning and Scheduling (ICAPS)}, author = {Wang, Qian and Veerapaneni, Rishi and Wu, Yu and Li, Jiaoyang and Likhachev, Maxim}, year = {2024}, pages = {623-632}, }
Improving Learnt Local MAPF Policies with Heuristic Search

Rishi Veerapaneni*, Qian Wang*, Kevin Ren*, Arthur Jakobsson*, Jiaoyang Li, and Maxim Likhachev

International Conference on Automated Planning and Scheduling (ICAPS), 2024

Abs arXiv Bib PDF Code

Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents to reach their goal locations. State-of-the-art classical MAPF solvers typically employ heuristic search to find solutions for hundreds of agents but are typically centralized and can struggle to scale when run with short timeouts. Machine learning (ML) approaches that learn policies for each agent are appealing as these could enable decentralized systems and scale well while maintaining good solution quality. Current ML approaches to MAPF have proposed methods that have started to scratch the surface of this potential. However, state-of-the-art ML approaches produce “local" policies that only plan for a single timestep and have poor success rates and scalability. Our main idea is that we can improve a ML local policy by using heuristic search methods on the output probability distribution to resolve deadlocks and enable full horizon planning. We show several model-agnostic ways to use heuristic search with learnt policies that significantly improve the policies’ success rates and scalability. To our best knowledge, we demonstrate the first time ML-based MAPF approaches have scaled to high congestion scenarios (e.g. 20% agent density).
@article{veerapaneni2024improving_mapf_policies_with_search, title = {Improving Learnt Local MAPF Policies with Heuristic Search}, volume = {34}, url = {https://ojs.aaai.org/index.php/ICAPS/article/view/31522}, doi = {10.1609/icaps.v34i1.31522}, number = {1}, journal = {International Conference on Automated Planning and Scheduling (ICAPS)}, author = {Veerapaneni, Rishi and Wang, Qian and Ren, Kevin and Jakobsson, Arthur and Li, Jiaoyang and Likhachev, Maxim}, year = {2024}, pages = {597-606}, }
Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution

Yifan Su, Rishi Veerapaneni, and Jiaoyang Li

AAAI Conference on Artificial Intelligence (AAAI), 2024

Abs arXiv Bib PDF

The Multi-Agent Path Finding (MAPF) problem involves planning collision-free paths for multiple agents in a shared environment. The majority of MAPF solvers rely on the assumption that an agent can arrive at a specific location at a specific timestep. However, real-world execution uncertainties can cause agents to deviate from this assumption, leading to collisions and deadlocks. Prior research solves this problem by having agents follow a Temporal Plan Graph (TPG), enforcing a consistent passing order at every location as defined in the MAPF plan. However, we show that TPGs are overly strict because, in some circumstances, satisfying the passing order requires agents to wait unnecessarily, leading to longer execution time. To overcome this issue, we introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG), which allows switching passing orders during execution to avoid unnecessary waiting time. We design two anytime algorithms for constructing a BTPG: BTPG-naïve and BTPG-optimized. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.
@article{su2024bidirectional_tpg, title = {Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution}, volume = {38}, url = {https://ojs.aaai.org/index.php/AAAI/article/view/29706}, doi = {10.1609/aaai.v38i16.29706}, number = {16}, journal = {AAAI Conference on Artificial Intelligence (AAAI)}, author = {Su, Yifan and Veerapaneni, Rishi and Li, Jiaoyang}, year = {2024}, pages = {17559-17566}, }

2023

Preprocessing-Based Planning for Utilizing Contacts in Semi-Structured High-Precision Insertion Tasks

Muhammad Suhail Saleem, Rishi Veerapaneni, and Maxim Likhachev

IEEE Robotics and Automation Letters (RAL), 2023

Abs Bib PDF

In manipulation tasks like plug insertion or assembly that have low tolerance to errors in pose estimation (errors of the order of 2 mm can cause task failure), the utilization of touch/contact modality can aid in accurately localizing the object of interest. Motivated by this, in this work we model high-precision insertion tasks as planning problems under pose uncertainty, where we effectively utilize the occurrence of contacts (or the lack thereof) as observations to reduce uncertainty and reliably complete the task. We present a preprocessing-based planning framework for high-precision insertion in repetitive and time-critical settings, where the set of initial pose distributions (identified by a perception system) is finite. The finite set allows us to enumerate the possible planning problems that can be encountered online and preprocess a database of policies. Due to the computational complexity of constructing this database, we propose a general experience-based POMDP solver, E-RTDP-Bel, that uses the solutions of similar planning problems as experience to speed up planning queries and use it to efficiently construct the database. We show that the developed algorithm speeds up database creation by over a factor of 100, making the process computationally tractable. We demonstrate the effectiveness of the proposed framework in a real-world plug insertion task in the presence of port position uncertainty and a pipe assembly task in simulation in the presence of pipe pose uncertainty.
@article{saleem2023preprocessing_contacts_planning, author = {Saleem, Muhammad Suhail and Veerapaneni, Rishi and Likhachev, Maxim}, journal = {IEEE Robotics and Automation Letters (RAL)}, title = {Preprocessing-Based Planning for Utilizing Contacts in Semi-Structured High-Precision Insertion Tasks}, year = {2023}, volume = {8}, number = {11}, pages = {6947-6954}, keywords = {Planning;Task analysis;Databases;Robot sensing systems;Uncertainty;Plugs;Location awareness;Manipulation planning;planning under uncertainty;reactive and sensor -based planning}, doi = {10.1109/LRA.2023.3309592}, }
Learning Local Heuristics for Search-Based Navigation Planning

Rishi Veerapaneni, Muhammad Suhail Saleem, and Maxim Likhachev

International Conference on Automated Planning and Scheduling (ICAPS), 2023

Abs Bib PDF

Graph search planning algorithms for navigation typically rely heavily on heuristics to efficiently plan paths. As a result, while such approaches require no training phase and can directly plan long horizon paths, they often require careful hand designing of informative heuristic functions. Recent works have started bypassing hand designed heuristics by using machine learning to learn heuristic functions that guide the search algorithm. While these methods can learn complex heuristic functions from raw input, they i) require significant training and ii) do not generalize well to new maps and longer horizon paths. Our contribution is showing that instead of learning a global heuristic estimate, we can define and learn local heuristics which results in a significantly smaller learning problem and improves generalization. We show that using such local heuristics can reduce node expansions by 2-20x while maintaining bounded suboptimality, are easy to train, and generalize to new maps & long horizon plans.
@article{veerapaneni2023local_heuristic_navigation, title = {Learning Local Heuristics for Search-Based Navigation Planning}, volume = {33}, url = {https://ojs.aaai.org/index.php/ICAPS/article/view/27245}, doi = {10.1609/icaps.v33i1.27245}, number = {1}, journal = {International Conference on Automated Planning and Scheduling (ICAPS)}, author = {Veerapaneni, Rishi and Saleem, Muhammad Suhail and Likhachev, Maxim}, year = {2023}, pages = {634-638}, }
Effective Integration of Weighted Cost-to-Go and Conflict Heuristic within Suboptimal CBS

Rishi Veerapaneni, Tushar Kusnur, and Maxim Likhachev

AAAI Conference on Artificial Intelligence (AAAI), 2023

Abs arXiv Bib PDF

Conflict-Based Search (CBS) is a popular multi-agent path finding (MAPF) solver that employs a low-level single agent planner and a high-level constraint tree to resolve conflicts. The vast majority of modern MAPF solvers focus on improving CBS by reducing the size of this tree through various strategies with few methods modifying the low level planner. Typically low level planners in existing CBS methods use an unweighted cost-to-go heuristic, with suboptimal CBS methods also using a conflict heuristic to help the high level search. In this paper, we show that, contrary to prevailing CBS beliefs, a weighted cost-to-go heuristic can be used effectively alongside the conflict heuristic in two possible variants. In particular, one of these variants can obtain large speedups, 2-100x, across several scenarios and suboptimal CBS methods. Importantly, we discover that performance is related not to the weighted cost-to-go heuristic but rather to the relative conflict heuristic weight’s ability to effectively balance low-level and high-level work. Additionally, to the best of our knowledge, we show the first theoretical relation of prioritized planning and bounded suboptimal CBS and demonstrate that our methods are their natural generalization. Update March 2024: We found that the relative speedup decreases to around 1.2-10x depending on how the conflict heuristic is computed (see appendix for more details).
@article{veerapaneni2023effective_integration_weecbs, title = {Effective Integration of Weighted Cost-to-Go and Conflict Heuristic within Suboptimal CBS}, volume = {37}, url = {https://ojs.aaai.org/index.php/AAAI/article/view/26381}, doi = {10.1609/aaai.v37i10.26381}, number = {10}, journal = {AAAI Conference on Artificial Intelligence (AAAI)}, author = {Veerapaneni, Rishi and Kusnur, Tushar and Likhachev, Maxim}, year = {2023}, pages = {11691-11698}, }

2022

Minimizing Coordination in Multi-Agent Path Finding with Dynamic Execution

Aidan Wagner*, Rishi Veerapaneni*, and Maxim Likhachev

AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2022

Abs Bib PDF

Multi-agent Path Finding (MAPF) is an important problem in large games with many dynamic agents that need to follow space-time trajectories without inter-agent collisions. Modern MAPF solvers plan assuming that agents directly follow the space-time trajectories at known constant speeds without delays or speedups, resulting in rigid plans which need to be replanned if there are changes during execution. Instead we would like agents to be able to follow their computed paths with dynamic velocities while requiring minimal coordination with others to prevent collisions and deadlocks. One way to address this problem is to first produce collision free space-time paths and then compute a coordination controller that prevents collisions and deadlock during dynamic execution. This two step process prevents fully minimizing coordination as the initially planned space-time paths do not reason about coordination and can be arbitrarily bad. We introduce a novel paradigm and show how planning in space-coordination level, rather than space-time, allows us to simultaneously plan paths and a coordination controller. Our method, Space-Level Conflict-Based Search (SL-CBS), builds on the Conflict-Based Search framework and allows us to reason explicitly about coordination, producing paths as well as a coordination controller with bounded suboptimal minimal coordination. We show experimentally that this results in a 20-50% reduction in coordination compared to the closest state of the art solver.
@article{wagner2022space_level_csb, title = {Minimizing Coordination in Multi-Agent Path Finding with Dynamic Execution}, volume = {18}, url = {https://ojs.aaai.org/index.php/AIIDE/article/view/21948}, doi = {10.1609/aiide.v18i1.21948}, number = {1}, journal = {AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE)}, author = {Wagner, Aidan and Veerapaneni, Rishi and Likhachev, Maxim}, year = {2022}, pages = {61-69}, }
Non-Blocking Batch A* (Technical Report)

Rishi Veerapaneni, and Maxim Likhachev

arXiv preprint arxiv:2208.07031, 2022

Abs arXiv Bib

Heuristic search has traditionally relied on hand-crafted or programmatically derived heuristics. Neural networks (NNs) are newer powerful tools which can be used to learn complex mappings from states to cost-to-go heuristics. However, their slow single inference time is a large overhead that can substantially slow down planning time in optimized heuristic search implementations. Several recent works have described ways to take advantage of NN’s batch computations to decrease overhead in planning, while retaining bounds on (sub)optimality. However, all these methods have used the NN heuristic in a "blocking" manner while building up their batches, and have ignored possible fast-to-compute admissible heuristics (e.g. existing classically derived heuristics) that are usually available to use. We introduce Non-Blocking Batch A* (NBBA*), a bounded suboptimal method which lazily computes the NN heuristic in batches while allowing expansions informed by a non-NN heuristic. We show how this subtle but important change can lead to substantial reductions in expansions compared to the current blocking alternative, and see that the performance is related to the information difference between the batch computed NN and fast non-NN heuristic.
@article{veerapaneni2022nonblocking, title = {Non-Blocking Batch A* (Technical Report)}, author = {Veerapaneni, Rishi and Likhachev, Maxim}, journal = {arXiv preprint arxiv:2208.07031}, year = {2022}, }

2020

Entity Abstraction in Visual Model-Based Reinforcement Learning

Rishi Veerapaneni*, John D. Co-Reyes*, Michael Chang*, Michael Janner, Chelsea Finn, Jiajun Wu, Joshua Tenenbaum, and Sergey Levine

In Conference on Robot Learning (CoRL), 2020

Abs arXiv Bib PDF Website

We present OP3, a framework for model-based reinforcement learning that acquires object representations from raw visual observations without supervision and uses them to predict and plan. To ground these abstract representations of entities to actual objects in the world, we formulate an interactive inference algorithm which incorporates dynamic information in the scene. Our model can handle a variable number of entities by symmetrically processing each object representation with the same locally-scoped function. On block-stacking tasks, OP3 can generalize to novel block configurations and more objects than seen during training, outperforming both a model that assumes access to object supervision and a state-of-the-art video prediction model.
@inproceedings{veerapaneni20entity_abstraction, title = {Entity Abstraction in Visual Model-Based Reinforcement Learning}, author = {Veerapaneni, Rishi and Co-Reyes, John D. and Chang, Michael and Janner, Michael and Finn, Chelsea and Wu, Jiajun and Tenenbaum, Joshua and Levine, Sergey}, booktitle = {Conference on Robot Learning (CoRL)}, pages = {1439--1456}, year = {2020}, editor = {Kaelbling, Leslie Pack and Kragic, Danica and Sugiura, Komei}, volume = {100}, series = {Proceedings of Machine Learning Research}, publisher = {PMLR}, url = {https://proceedings.mlr.press/v100/veerapaneni20a}, }

2018

Tricking Neural Networks: Create Your Own Adversarial Examples

Daniel Geng, and Rishi Veerapaneni

Machine Learning @ Berkeley, 2018

Abs Bib Website

This article explains what adversarial examples are and how to create your different types of adversarial examples for neural networks.
@article{geng2018adversarial_examples, title = {Tricking Neural Networks: Create Your Own Adversarial Examples}, author = {Geng, Daniel and Veerapaneni, Rishi}, journal = {Machine Learning @ Berkeley}, year = {2018}, }

2017

Adaptive Estimation of Active Contour Parameters Using Convolutional Neural Networks and Texture Analysis

Assaf Hoogi, Arjun Subramaniam*, Rishi Veerapaneni*, and Daniel L. Rubin

IEEE Transactions on Medical Imaging, 2017

Abs Bib PDF

We propose a generalization of the level set segmentation approach by supplying a novel method for adaptive estimation of active contour parameters. The presented segmentation method is fully automatic once the lesion has been detected. First, the location of the level set contour relative to the lesion is estimated using a convolutional neural network (CNN). The CNN has two convolutional layers for feature extraction, which lead into dense layers for classification. Second, the output CNN probabilities are then used to adaptively calculate the parameters of the active contour functional during the segmentation process. Finally, the adaptive window size surrounding each contour point is re-estimated by an iterative process that considers lesion size and spatial texture. We demonstrate the capabilities of our method on a dataset of 164 MRI and 112 CT images of liver lesions that includes low contrast and heterogeneous lesions as well as noisy images. To illustrate the strength of our method, we evaluated it against state of the art CNN-based and active contour techniques. For all cases, our method, as assessed by Dice similarity coefficients, performed significantly better than currently available methods. An average Dice improvement of 0.27 was found across the entire dataset over all comparisons. We also analyzed two challenging subsets of lesions and obtained a significant Dice improvement of 0.24 with our method (p <;0.001, Wilcoxon).
@article{hoogi2017adaptive_segmentation, author = {Hoogi, Assaf and Subramaniam, Arjun and Veerapaneni, Rishi and Rubin, Daniel L.}, journal = {IEEE Transactions on Medical Imaging}, title = {Adaptive Estimation of Active Contour Parameters Using Convolutional Neural Networks and Texture Analysis}, year = {2017}, volume = {36}, number = {3}, pages = {781-791}, keywords = {Lesions;Level set;Image segmentation;Active contours;Adaptation models;Adaptive estimation;Neural networks;Active contours;adaptive parameters;convolutional neural network;image segmentation}, doi = {10.1109/TMI.2016.2628084}, }