Full plan for three agents
Explanations of the full plan in 3 parts for quick validation
As we begin employing teams of robots to accomplish complex tasks, it becomes difficult for a human to verify that future paths do not result in collisions. Therefore, we are working on new multiagent planning approaches that minimize the effort it takes a human to verify the paths.
Multi-agent motion planning (MMP) is the problem of finding a motion plan for multiple agents such that when these agents are run simultaneously, none of the agents collide. These motion plans are traditionally computed using provably correct algorithms and immediately executed on a real system. In safety-critical applications, however, a human supervisor may want to verify that the plan is indeed collision-free prior to execution. This process can be extremely unintuitive since MMP solutions commonly have intersecting lines, making it difficult to verify that the agents do not collide. The inability for humans to validate traditional MMP algorithms leaves a huge trust-gap between motion planning experts and the daily-users who could benefit from using such algorithms. This work focuses on shortening the gap by incorporating explainability into traditional MMP algorithms.
We investigate the notion of an explanation for a plan of MMP, based on visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint, clearly illustrating the safety of the plan. Presenting the plan in this way makes it very easy for a human to recognize the plan is collision free because recognizing line intersections happens very early in the cognitive process. Giving MMP algorithms the ability to explain their solutions to humans would greatly shorten the trust-gap between motion planning research experts and daily-users of these algorithms, consequentially allowing MMP algorithms to be further utilized within safety-critical systems.
2023
-
A. Theurkauf, J. Kottinger, N. Ahmed, and M. Lahijanian, “Chance-Constrained Multi-Robot Motion Planning Under Gaussian Uncertainties,” IEEE Robotics and Automation Letters, vol. 9, no. 1, pp. 835–842, Dec. 2023.
@article{Theurkauf:RAL:2023,
author = {Theurkauf, Anne and Kottinger, Justin and Ahmed, Nisar and Lahijanian, Morteza},
journal = {IEEE Robotics and Automation Letters},
title = {Chance-Constrained Multi-Robot Motion Planning Under Gaussian Uncertainties},
year = {2023},
volume = {9},
number = {1},
pages = {835-842},
doi = {10.1109/LRA.2023.3337700},
url = {https://arxiv.org/abs/2303.11476},
month = dec,
videourl = {https://youtu.be/ilAlZaoieKg?si=GWa8FD1RHEuJbRlE},
bibkey = {ma-planning}
}
We consider a chance-constrained multi-robot motion planning problem in the presence of Gaussian motion and sensor noise. Our proposed algorithm, CC-K-CBS, leverages the scalability of kinodynamic conflict-based search (K-CBS) in conjunction with the efficiency of Gaussian belief trees as used in the Belief-A framework, and inherits the completeness guarantees of Belief-A’s low-level sampling-based planner. We also develop three different methods for robot-robot probabilistic collision checking, which trade off computation with accuracy. Our algorithm generates motion plans driving each robot from its initial to goal state while accounting for uncertainty evolution with chance-constrained safety guarantees. Benchmarks compare computation time to conservatism of the collision checkers, in addition to characterizing the performance of the planner as a whole. Results show that CC-K-CBS scales up to 30 robots.
2022
-
J. Kottinger, S. Almagor, and M. Lahijanian, “Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints,” in Int’l Conference on Intelligent Robots and Systems (IROS), Kyoto, Japan, 2022.
@inproceedings{Kottinger:IROS:2022,
title = {Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints},
author = {Kottinger, Justin and Almagor, Shaull and Lahijanian, Morteza},
booktitle = {Int'l Conference on Intelligent Robots and Systems (IROS)},
year = {2022},
address = {Kyoto, Japan},
month = oct,
publisher = {IEEE},
note = {},
doi = {10.1109/IROS47612.2022.9982018},
url = {https://arxiv.org/abs/2207.00576},
videourl = {https://youtu.be/O39gmj5WVwE},
bibkey = {ma-planning}
}
Multi-robot motion planning (MRMP) is the fundamental problem of finding non-colliding trajectories for multiple robots acting in an environment, under kinodynamic constraints. Due to its complexity, existing algorithms are either incomplete, or utilize simplifying assumptions. This work introduces Kinodynamic Conflict-Based Search (K-CBS), a decentralized MRMP algorithm that is general, scalable, and probabilistically complete. The algorithm takes inspiration from successful solutions to the discrete analogue of MRMP over finite graphs, known as Multi-Agent Path Finding (MAPF). Specifically, we adapt ideas from Conflict-Based Search (CBS)-a popular decentralized MAPF algorithm-to the MRMP setting. The novelty of our approach is that we work directly in the continuous domain, without discretization. In particular, the kinodynamic constraints are treated natively. K-CBS plans for each robot individually using a low-level planner and grows a conflict tree to resolve collisions between robots by defining constraints. The low-level planner can be any sampling-based, tree-search algorithm for kinodynamic robots, thus lifting existing planners for single robots to the multi-robot setting. We show that K-CBS inherits the (probabilistic) completeness of the low-level planner. We illustrate the generality and performance of K-CBS in several case studies and benchmarks.
-
J. Kottinger, S. Almagor, and M. Lahijanian, “Conflict-Based Search for Explainable Multi-Agent Path Finding,” in Int’l Conference on Automated Planning and Scheduling (ICAPS), Singapore, 2022.
@inproceedings{Kottinger:ICAPS:2022,
title = {Conflict-Based Search for Explainable Multi-Agent Path Finding},
author = {Kottinger, Justin and Almagor, Shaull and Lahijanian, Morteza},
booktitle = {Int'l Conference on Automated Planning and Scheduling (ICAPS)},
year = {2022},
address = {Singapore},
month = jun,
publisher = {AAAI Press},
doi = {10.1609/icaps.v32i1.19859},
url = {https://arxiv.org/abs/2202.09930},
videourl = {https://youtu.be/UeZR3IzVbwM},
bibkey = {ma-planning}
}
The goal of the Multi-Agent Path Finding (MAPF) problem is to find non-colliding paths for agents in an environment, such that each agent reaches its goal from its initial location. In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. To this end, a recent work introduces a notion of explainability for MAPF based on a visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint. Then, the problem of Explainable MAPF via Segmentation asks for a set of non-colliding paths that admit a short-enough explanation. Explainable MAPF adds a new difficulty to MAPF, in that it is NP-hard with respect to the size of the environment, and not just the number of agents. Thus, traditional MAPF algorithms are not equipped to directly handle Explainable MAPF. In this work, we adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle Explainable MAPF. We show how to add explainability constraints on top of the standard CBS tree and its underlying A* search. We examine the usefulness of this approach and, in particular, the trade-off between planning time and explainability.
2021
-
J. Kottinger, S. Almagor, and M. Lahijanian, “MAPS-X: Explainable Multi-Robot Motion Planning via Segmentation,” in Int’l Conference on Robotics and Automation (ICRA), Xi’an, China, 2021.
@inproceedings{Kottinger:ICRA:2021,
title = {{MAPS-X}: Explainable Multi-Robot Motion Planning via Segmentation},
author = {Kottinger, Justin and Almagor, Shaull and Lahijanian, Morteza},
booktitle = {Int'l Conference on Robotics and Automation (ICRA)},
year = {2021},
address = {Xi'an, China},
month = may,
publisher = {IEEE},
bibkey = {ma-planning},
doi = {10.1109/ICRA48506.2021.9561893},
url = {https://arxiv.org/abs/2010.16106},
videourl = {https://youtu.be/82VLQtOtZ8I}
}
Traditional multi-robot motion planning (MMP) focuses on computing trajectories for multiple robots acting in an environment, such that the robots do not collide when the trajectories are taken simultaneously. In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. In this work, we propose a notion of explanation for a plan of MMP, based on visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint, clearly illustrating the safety of the plan. We show that standard notions of optimality (e.g., makespan) may create conflict with short explanations. Thus, we propose meta-algorithms, namely multi-agent plan segmenting-X (MAPS-X) and its lazy variant, that can be plugged on existing centralized sampling-based tree planners X to produce plans with good explanations using a desirable number of images. We demonstrate the efficacy of this explanation-planning scheme and extensively evaluate the performance of MAPS-X and its lazy variant in various environments and agent dynamics.
2020
-
-
S. Almagor and M. Lahijanian, “Explainable Multi Agent Path Finding,” in Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, Richland, SC, 2020, pp. 34–42.
@inproceedings{Almagor:AAMAS:2020,
author = {Almagor, Shaull and Lahijanian, Morteza},
title = {Explainable Multi Agent Path Finding},
year = {2020},
isbn = {9781450375184},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
address = {Richland, SC},
booktitle = {Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems},
pages = {34–-42},
numpages = {9},
keywords = {path planning, mapf, explainability, motion planning, path finding, multi-agent systems},
location = {Auckland, New Zealand},
series = {AAMAS ’20},
bibkey = {ma-planning},
doi = {https://dl.acm.org/doi/abs/10.5555/3398761.3398771},
url = {https://shaull.github.io/pub/AL20.pdf}
}
Multi Agent Path Finding (MAPF) is the problem of planning paths for agents to reach their targets from their start locations, such that the agents do not collide while executing the plan. In safety-critical systems, the plan is typically checked by a human supervisor, who decides on whether to allow its execution. In such cases, we wish to convince the human that the plan is indeed collision free.To this end, we propose an explanation scheme for MAPF, which bases explanations on simplicity of visual verification by human’s cognitive process. The scheme decomposes a plan into segments such that within each segment, the paths of the agents are disjoint. Then, we can convince the supervisor that the plan is collision free using a small number of images (dubbed an explanation). In addition, we can measure the simplicity of a plan by the number of segments required for the decomposition. We study the complexity of algorithmic problems that arise by the explanation scheme, as well as the tradeoff between the length (makespan) of a plan and its minimal decomposition. We also provide experimental results of our scheme both in a continuous and in a discrete setting.