Related Publications
Scalable Multi-Robot Motion Planning Using Guidance-Informed Hypergraphs, Courtney McBeth, James Motes, Isaac Ngui, Marco Morales, Nancy M. Amato, ArXiv Preprint, Jun 2024.
Keywords: Motion Planning, Multi-Agent, Workspace Topology
Links : [ArXiv]
BibTex
@misc{mcbeth2024scalablemultirobotmotionplanning,
title={Scalable Multi-Robot Motion Planning Using Guidance-Informed Hypergraphs},
author={Courtney McBeth and James Motes and Isaac Ngui and Marco Morales and Nancy M. Amato},
year={2024},
eprint={2311.10176},
archivePrefix={arXiv},
primaryClass={cs.RO},
url={https://arxiv.org/abs/2311.10176},
}
Abstract
In this work, we present a multi-robot planning framework that leverages guidance about the problem to efficiently search the planning space. This guidance captures when coordination between robots is necessary, allowing us to decompose the intractably large multi-robot search space while limiting risk of inter-robot conflicts by composing relevant robot groups together while planning. Our framework additionally supports planning with kinodynamic constraints through our conflict resolution structure. This structure also improves the scalability of our approach by eliminating unnecessary work during the construction of motion solutions. We also provide an application of this framework to multiple mobile robot motion planning in congested environments using topological guidance. Our previous work has explored using topological guidance, which utilizes information about the robots' environment, in these multi-robot settings where a high degree of coordination is required of the full robot group. In real-world scenarios, this high level of coordination is not always necessary and results in excessive computational overhead. Here, we leverage our novel framework to achieve a significant improvement in scalability and show that our method efficiently finds paths for robot teams up to an order of magnitude larger than existing state-of-the-art methods in congested settings with narrow passages in the environment.
Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning, Irving Solis, James Motes, Mike Qin, Marco Morales, Nancy M. Amato, IEEE Robotics and Automation Letters, Vol: 9, Issue: 8, pp. 7238-7245, Jun 2024. DOI: 10.1109/LRA.2024.3420548
Keywords: Motion Planning, Multi-Agent Systems, Sampling-Based Motion Planning
Links : [Published] [ArXiv] [Video]
BibTex
@ARTICLE{10577245,
author={Solis, Irving and Motes, James and Qin, Mike and Morales, Marco and Amato, Nancy M.},
journal={IEEE Robotics and Automation Letters},
title={Adaptive Robot Coordination: A Subproblem-Based Approach for Hybrid Multi-Robot Motion Planning},
year={2024},
volume={9},
number={8},
pages={7238-7245},
keywords={Robots;Robot kinematics;Planning;Space exploration;Probabilistic logic;Mobile robots;Collision avoidance;Path planning for multiple mobile robots or agents;multi-robot systems;motion and path planning},
doi={10.1109/LRA.2024.3420548}}
Abstract
This work presents Adaptive Robot Coordination (ARC), a novel hybrid framework for multi-robot motion planning (MRMP) that employs local subproblems to resolve inter-robot conflicts. ARC creates subproblems centered around conflicts, and the solutions represent the robot motions required to resolve these conflicts. The use of subproblems enables an innovative, cost-effective hybrid exploration of the multi-robot planning space by dynamically coupling and decoupling necessary subsets of robots only when required and in specific physical locations. This allows ARC to adapt the levels of coordination efficiently by planning in decoupled spaces, where robots can operate independently, and in coupled spaces, where coordination is essential. ARC is probabilistically complete, can be used for any robot, and produces cost-efficient solutions in reduced planning times. Through extensive evaluation across representative scenarios with different robots requiring various levels of coordination, ARC demonstrates its ability to provide simultaneous scalability and precise coordination. ARC is the only method capable of solving all the scenarios and is competitive with coupled, decoupled, and hybrid baselines.
A Hierarchical Approach to Workstation-based Task Allocation and Motion Planning, Isaac Ngui, Seongwon Lee, James Motes, Marco Morales, Nancy M. Amato, IROS 2023, May 2024. DOI: Unpublished
Keywords: Multi-Agent Systems, Path Planning, Task Planning
Links :
BibTex
Unpublished
Abstract
This paper introduces a hierarchical approach to workstation-based task allocation and motion planning problems for on-demand and reconfigurable factory environments.
This problem is composed of two sub-problems: workstation task planning and payload transportation.
This hierarchical approach abstracts away workstation details during payload transportation and payload transportation details away during workstation task planning, enabling scalable planning for large numbers of robots and workstations.
This hierarchical approach is expected to offer adaptable solutions for various workstation-based factory scenarios, promoting high throughput while maintaining flexibility.
Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance, Courtney McBeth, James Motes, Diane Uwacu, Marco Morales, Nancy M. Amato, In IEEE Robotics and Automation Letters, Aug 2023. DOI: 10.1109/LRA.2023.3312980
Keywords: Motion Planning, Multi-Agent, Workspace Topology
Links : [Published] [ArXiv] [Video]
BibTex
@ARTICLE{10243143,
author={McBeth, Courtney and Motes, James and Uwacu, Diane and Morales, Marco and Amato, Nancy M.},
journal={IEEE Robotics and Automation Letters},
title={Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance},
year={2023},
volume={},
number={},
pages={1-8},
doi={10.1109/LRA.2023.3312980}}
Abstract
Multi-robot motion planning (MRMP) is the problem of finding collision-free paths for a set of robots in a continuous state space. The difficulty of MRMP increases with the number of robots and is exacerbated in environments with narrow passages that robots must pass through, like warehouse aisles where coordination between robots is required. In single-robot settings, topology-guided motion planning methods have shown improved performance in these constricted environments. In this work, we extend an existing topology-guided single-robot motion planning method to the multi-robot domain to leverage the improved efficiency provided by topological guidance. We demonstrate our method's ability to efficiently plan paths in complex environments with many narrow passages, scaling to robot teams of size up to 25 times larger than existing methods in this class of problems. By leveraging knowledge of the topology of the environment, we also find higher-quality solutions than other methods.
Parallel Hierarchical Composition Conflict-Based Search, Hannah Lee, James Motes, Marco Morales, Nancy M. Amato, IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol: 6, Issue: 4, pp. 7001-7008, Prague, Czech Republic, Jul 2021. DOI: 10.1109/LRA.2021.3096476.
Keywords: Multi-Agent, Parallel Planning, Path Planning
Links : [Published]
BibTex
@article{lee2021parallel,
title={Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding},
author={Lee, Hannah and Motes, James and Morales, Marco and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},
volume={6},
number={4},
pages={7001--7008},
year={2021},
publisher={IEEE}
}
Abstract
In this letter, we present the following optimal multi-agent pathfinding (MAPF) algorithms: Hierarchical Composition Conflict-Based Search, Parallel Hierarchical Composition Conflict-Based Search, and Dynamic Parallel Hierarchical Composition Conflict-Based Search. MAPF is the task of finding an optimal set of valid path plans for a set of agents such that no agents collide with present obstacles or each other. The presented algorithms are an extension of Conflict-Based Search (CBS), where the MAPF problem is solved by composing and merging smaller, more easily manageable subproblems. Using the information from these subproblems, the presented algorithms can more efficiently find an optimal solution. Our three presented algorithms demonstrate improved performance for optimally solving MAPF problems consisting of many agents in crowded areas while examining fewer states when compared with CBS and its variant Improved Conflict-Based Search.
Avoidance Critical Probabilistic Roadmaps for Motion Planning in Dynamic Environments, Felipe Felix Arias, Brian Ichter, Aleksandra Faust, Nancy M. Amato, IEEE International Conference on Robotics and Automation (ICRA), Xien, China, Jun 2021. DOI: Published
Keywords: Machine Learning, Mobile Robots, Spatial Awareness
Links : [Published] [Video]
BibTex
@inproceedings{50155,
title = {Avoidance Critical Probabilistic Roadmaps for Motion Planning in Dynamic Environments},
author = {Felipe Felix Arias and Brian Andrew Ichter and Aleksandra Faust and Nancy M. Amato},
year = {2021},
booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}
}
Abstract
Motion planning among dynamic obstacles is an essential capability towards navigation in the real-world. Sampling-based motion planning algorithms find solutions by approximating the robotâÂÂs configuration space through a graph representation, predicting or computing obstaclesâ trajectories, and finding feasible paths via a pathfinding algorithm. In this work, we seek to improve the performance of these subproblems by identifying regions critical to dynamic environment navi- gation and leveraging them to construct sparse probabilistic roadmaps. Motion planning and pathfinding algorithms should allow robots to prevent encounters with obstacles, irrespective of their trajectories, by being conscious of spatial context cues such as the location of chokepoints (e.g., doorways). Thus, we propose a self-supervised methodology for learning to identify regions frequently used for obstacle avoidance from local environment features. As an application of this concept, we leverage a neural network to generate hierarchical probabilistic roadmaps termed Avoidance Critical Probabilistic Roadmaps (ACPRM). These roadmaps contain motion structures that enable efficient obstacle avoidance, reduce the search and planning space, and increase a roadmapâÂÂs reusability and coverage. ACPRMs are demonstrated to achieve up to five orders of magnitude improvement over grid-sampling in the multi-agent setting and up to ten orders of magnitude over a competitive baseline in the multi-query setting.
Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search, Irving Solis, James Motes, Read Sandström, Nancy M. Amato, IEEE Robotics and Automation Letters, Mar 2021. DOI: https://doi.org/10.1109/LRA.2021.3068910
Keywords: Industrial Applications, Motion Planning, Multi-Agent
Links : [Published] [Manuscript]
BibTex
@article{solis2019representation,
title={Representation-optimal multi-robot motion planning using conflict-based search},
author={Solis, Irving and Sandstr{\"o}m, Read and Motes, James and Amato, Nancy M},
journal={arXiv preprint arXiv:1909.13352},
year={2019}
}
Abstract
Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents each with individual start and goal states within a continuous state space. Existing approaches can be split into coupled methods which provide optimal solutions but struggle with scalability or decoupled methods which provide scalable solutions but offer no optimality guarantees. Recent work has explored hybrid approaches that leverage the advantages of both coupled and decoupled approaches in an easier discrete subproblem, Multi-Agent Pathfinding (MAPF). In this work, we adapt recent developments in hybrid MAPF to the continuous domain of MAMP. We demonstrate the scalability of our method to manage groups of up to 32 agents, demonstrate the ability to handle up to 8 high-DOF manipulators, and plan for heterogeneous teams. In all scenarios, our approach plans significantly faster while providing higher quality solutions.
Robust Online Belief Space Planning in Changing Environments: Application to Physical Mobile Robots, Ali-akbar Agha-mohammadi, Saurav Agarwal, Aditya Mahadevan, Suman Chakravorty, Daniel Tomkins, Jory Denny, Nancy M. Amato, 2014 IEEE International Conference on Robotics and Automation (ICRA), pp. 149-156, Hong Kong, China, May 2014. DOI: 10.1109/ICRA.2014.6906602
Keywords: Belief Space, Mobile Robots, Sampling-Based Motion Planning
Links : [Published] [Manuscript]
BibTex
@INPROCEEDINGS{6906602, author={A. {Agha-mohammadi} and S. {Agarwal} and A. {Mahadevan} and S. {Chakravorty} and D. {Tomkins} and J. {Denny} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={Robust online belief space planning in changing environments: Application to physical mobile robots}, year={2014}, volume={}, number={}, pages={149-156}, doi={10.1109/ICRA.2014.6906602}}
Abstract
Motion planning in belief space (under motion and sensing uncertainty) is a challenging problem due to the computational intractability of its exact solution. The Feedback-based Information RoadMap (FIRM) framework made an important theoretical step toward enabling roadmap-based planning in belief space and provided a computationally tractable version of belief space planning. However, there are still challenges in applying belief space planners to physical systems, such as the discrepancy between computational models and real physical models. In this paper, we propose a dynamic replanning scheme in belief space to address such challenges. Moreover, we present techniques to cope with changes in the environment (e.g., changes in the obstacle map), as well as unforeseen large deviations in the robot's location (e.g., the kidnapped robot problem). We then utilize these techniques to implement the first online replanning scheme in belief space on a physical mobile robot that is robust to changes in the environment and large disturbances. This method demonstrates that belief space planning is a practical tool for robot motion planning.
Analysis of the Evolution of C-Space Models Built through Incremental Exploration, Marco Morales, Roger Pearce, Nancy M. Amato, in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1029-1034, Rome, Italy, Apr 2007. DOI: 10.1109/ROBOT.2007.363120
Keywords: Mobile Robots, Motion Planning, Sampling-Based Motion Planning
Links : [Published]
BibTex
@INPROCEEDINGS{4209224,
author={Morales, Marco and Pearce, Roger and Amato, Nancy M.},
booktitle={Proceedings 2007 IEEE International Conference on Robotics and Automation},
title={Analysis of the Evolution of C-Space Models built through Incremental Exploration},
year={2007},
volume={},
number={},
pages={1029-1034},
doi={10.1109/ROBOT.2007.363120}}
Abstract
Many sampling methods for motion planning explore the robot's configuration space (C-space) starting from a set of configuration(s) and incrementally explore surrounding areas to produce a growing model of the space. Although there is a common understanding of the strengths and weaknesses of these techniques, metrics for analyzing the incremental exploration process and for evaluating the performance of incremental samplers have been lacking. We propose the use of local metrics that provide insight into the complexity of the different regions in the model and global metrics that describe the process as a whole. These metrics only require local information and can be efficiently computed. We illustrate the use of our proposed metrics to analyze representative incremental strategies including the rapidly-exploring random trees, expansive space trees, and the original randomized path planner. We show how these metrics model the efficiency of C-space exploration and help to identify different modeling stages. In addition, these metrics are ideal for adapting space exploration to improve performance.
Enveloping multi-pocket obstacles with hexagonal metamorphic robots, Jennifer E. Walter, Mary E. Brooks, David F. Little, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Vol: 3, pp. 2204-2209, New Orleans, Louisiana, USA, Apr 2004. DOI: 10.1109/ROBOT.2004.1307389
Keywords: Mobile Robots, Motion Planning, Multi-Agent
Links : [Published]
BibTex
@INPROCEEDINGS{1307389,
author={J. E. {Walter} and M. E. {Brooks} and D. F. {Little} and N. M. {Amato}},
booktitle={IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004}, title={Enveloping multi-pocket obstacles with hexagonal metamorphic robots},
year={2004},
volume={3},
number={},
pages={2204-2209 Vol.3},
doi={10.1109/ROBOT.2004.1307389}}
Abstract
The problem addressed is reconfiguration planning for a metamorphic robotic system composed of any number of hexagonal robots when a single obstacle with multiple indentations or "pockets" is embedded in the goal environment. We extend our earlier work on filling a single pocket in an obstacle to the case where the obstacle surface may contain multiple pockets. The planning phase of our algorithm first determines whether the obstacle pockets provide sufficient clearance for module movement, i.e., whether the obstacle is "admissible". In this paper, we present algorithms that sequentially order individual pockets and order module placement inside each pocket. These algorithms ensure that every cell in each pocket is filled and that module deadlock and collision do not occur during reconfiguration. This paper also provides a complete overview of the planning stage that is executed prior to reconfiguration and presents a distributed reconfiguration schema for filling more than one obstacle pocket concurrently, followed by the envelopment of the entire obstacle. Lastly, we present examples of obstacles with multiple pockets that were successfully filled using our distributed reconfiguration simulator.
Feature-Based Localization using Scannable Visibility Sectors, Jinsuck Kim, Roger A. Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Vol: 2, pp. 2854-2859, Taipei, Taiwan, Sep 2003. DOI: 10.1109/ROBOT.2003.1242025
Keywords: Mobile Robots, Navigation, Sensor Systems
Links : [Published]
BibTex
@INPROCEEDINGS{1242025,
author={ {Jinsuck Kim} and R. A. {Pearce} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={Feature-based localization using scannable visibility sectors},
year={2003},
volume={2},
number={},
pages={2854-2859 vol.2},
doi={10.1109/ROBOT.2003.1242025}}
Abstract
This paper presents methods for navigating and localizing mobile robots in a known indoor environment. We introduce a restricted visibility concept called a scannable sector that can aid many existing navigation and localization algorithms. The scannable sectors are based on the physical characteristics of the environment and the limitations of the localization sensors used. We describe a complete navigation system that includes a scannable sector based localizer, sonar sensors, and a probabilistic roadmap path planner. Simulation and hardware results using a real robot with sonar sensors show the potential of our approach.
Enveloping Obstacles with Hexagonal Metamorphic Robots, Jennifer E. Walter, Mary E. Brooks, David F. Little, Nancy M. Amato, Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Vol: 1, pp. 741-748, Taipei, Taiwan, Jan 2003. DOI: 10.1109/ROBOT.2003.1241682
Keywords: Mobile Robots, Motion Planning, Multi-Agent
Links : [Published]
BibTex
@INPROCEEDINGS{1241682,
author={J. E. {Walter} and E. M. {Tsai} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={Enveloping obstacles with hexagonal metamorphic robots},
year={2003},
volume={1},
number={},
pages={741-748 vol.1},
doi={10.1109/ROBOT.2003.1241682}}
Abstract
The problem addressed is the distributed reconfiguration of the metamorphic robot system composed of any number of two dimensional robots (modules). The initial configuration we consider is a straight chain of modules, while the goal configuration satisfies a simple admissibility condition. Our reconfiguration strategy depends on finding a contiguous path of cells, called a substrate path that spans the goal configuration. Modules fill in this substrate path and then move along the path to fill in the remainder of the goal without collision or deadlock. In this paper, we address the problem of reconfiguration when a single obstacle is embedded in the goal environment. We introduce a classification for traversable surfaces, which allows for coherence in defining admissibility characteristics for various objects in the hexagonal grid. We present algorithms to 1) determine if an obstacle embedded in the goal fulfills a simple admissibility requirement, 2) include an admissible obstacle in a substrate path, and 3) accomplish distributed reconfiguration.
An Integrated Mobile Robot Path (Re)Planner and Localizer for Personal Robots, Jinsuck Kim, Nancy Amato, Sooyong Lee, In Proc. IEEE International Conference on Robotics and Automation (ICRA), Seoul, South Korea, May 2001. DOI: 10.1109/ROBOT.2001.933208
Keywords: Mobile Robots, Motion Planning
Links : [Published]
BibTex
@INPROCEEDINGS{933208, author={ {Jinsuck Kim} and N. M. {Amato} and {Sooyong Lee}}, booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164)}, title={An integrated mobile robot path (re)planner and localizer for personal robots}, year={2001}, volume={4}, number={}, pages={3789-3794 vol.4}, doi={10.1109/ROBOT.2001.933208}}
Abstract
We describe a method for navigation in a known indoor environment, such as a home or office, that requires only inexpensive range sensors. Our framework includes a high-level planner which integrates and coordinates path planning and localization modules with the aid of a module for computing regions which are expected, with high probability, to contain the robot at any given time. The localization method is based on simple geometric properties of the environment which are computed during a preprocessing stage. The roadmap-based path planner enables one to select routes, and subgoals along those routes, that will facilitate localization and other optimization criteria. In addition, our framework enables one to quickly plan new routes, dynamically, based on the current position as computed by intermediate localization operations. We present simulation and hardware experimental results that illustrate the practicality and potential of our approach.