Multi-Robot
Related: Multi-Agent Systems  

Current Contributors: James Motes, Irving Solis, Courtney McBeth, Nancy Amato
Project Alumni: Read Sandström, O. Burchan Bayazit, Jyh-Ming Lien, Sam Rodriguez, Jory Denny, Aditya Mahadevan, Daniel Tomkins, Roger Pearce, Sooyong Lee, Jinsuck Kim, Ali Agha-mohammadi, Saurav Agarwal, Aditya Mahadevan, Suman Chakravorty (Aerospace Engineering, TAMU)
Interns and undergrad students: Jose Carrillo

Supported By: NSF
We present several projects that integrate multi-agent simulation with roadmap-based path planning to support a wide variety of multi-agent systems problems. We show an adaptation of a discrete algorithm to solve the Multi-Agent Motion Planning problem in continuous spaces. We also investigate in different ways how agents can work cooperatively to perform tasks, plan paths in dynamic environments, or influence another group of agents to locations in an environment.



Multi-Agent Motion Planning


We show an adaptation of a discrete algorithm to solve the Multi-Agent Motion Planning problem in continuous spaces.

Group Behaviors


We investigate different ways in how groups of agents can work cooperatively and accomplish specific tasks by acquiring different types of behaviors.

Mobile Robots


We explore different tasks for mobile robots, such as navigation, localization and coverage

Multi-robot Guided Planning


We investigate the use of topological guidance to efficiently solve the Multi-robot Motion Planning problem.

Related Publications

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, Multi-Agent
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.


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.


Toward Realistic Pursuit-Evasion Using a Roadmap-Based Approach, Samuel Rodriguez, Jory Denny, Juan Burgos, Aditya Mahadevan, Kasra Manavi, Luke Murray, Anton Kodochygov, Takis Zourntos, and Nancy M. Amato, IEEE International Conference on Robotics and Automation, Shanghai, China, May 2011. DOI: 10.1109/ICRA.2011.5980467
Keywords: Group Behavior, Multi-Agent, Sampling-Based Motion Planning
Links : [Published]

BibTex

@inproceedings{rodriguez2011toward,
title={Toward realistic pursuit-evasion using a roadmap-based approach},
author={Rodriguez, Samuel and Denny, Jory and Burgos, Juan and Mahadevan, Aditya and Manavi, Kasra and Murray, Luke and Kodochygov, Anton and Zourntos, Takis and Amato, Nancy M},
booktitle={2011 IEEE International Conference on Robotics and Automation},
pages={1738--1745},
year={2011},
organization={IEEE}
}


Abstract

In this work, we describe an approach for modeling and simulating group behaviors for pursuit-evasion that uses a graph-based representation of the environment and integrates multi-agent simulation with roadmap-based path planning. Our approach can be applied to more realistic scenarios than are typically studied in most previous work, including agents moving in 3D environments such as terrains, multi-story buildings, and dynamic environments. We also support more realistic three-dimensional visibility computations that allow evading agents to hide in crowds or behind hills. We demonstrate the utility of this approach on mobile robots and in simulation for a variety of scenarios including pursuit-evasion and tag on terrains, in multi-level buildings, and in crowds.


Utilizing Roadmaps in Evacuation Planning, Samuel Rodriguez, Nancy M. Amato, The International Journal of Virtual Reality, Vol: 10, Issue: 1, Jan 2011. DOI: https://doi.org/10.20870/IJVR.2011.10.1.2804
Keywords: Motion Planning
Links : [Published]

BibTex

@article{rodriguez2011utilizing,
title={Utilizing roadmaps in evacuation planning},
author={Rodriguez, Samuel and Amato, Nancy M},
journal={International Journal of Virtual Reality},
volume={10},
number={1},
pages={67--73},
year={2011}
}


Abstract

In this paper we describe utilization of roadmaps in a general evacuation planning system for complex 3D environments. The problem consists of heterogeneous groups of agents whose behaviors and properties affect usage of the environment when creating evacuation plans. This planning system includes behaviors for those agents evacuating and directors that may be guiding the agents to improve evacuation. One aspect we focus on is modeling different forms of direction and communication between agents.


Roadmap-Based Pursuit-Evasion in 3D Structures, Samuel Rodriguez, Jory Denny, Aditya Mahadevan, Jeremy Vu, Juan Burgos, Takis Zourntos, and Nancy M. Amato, International Conference on Computer Animation and Social Agents, Jan 2011.
Keywords: Motion Planning
Links : [Published]

BibTex

@inproceedings{rodriguez2011roadmap,
title={Roadmap-based pursuit-evasion in 3d structures},
author={Rodriguez, Samuel and Denny, Jory and Mahadevan, Aditya and Vu, Jeremy and Burgos, Juan and Zourntos, Takis and Amato, Nancy M},
booktitle={24th Intern. Conf. on Computer Animation and Social Agents (CASA)},
year={2011},
organization={Citeseer}
}


Abstract

We present an approach to the pursuit-evasion problem which is applicable to complex, multi-level environments. Studying each aspect of this problem in 3D structured environments is a distinct extension over many previous approaches. We also utilize our roadmap-based approach to multi-agent behavior when tracking agents of interest. Results are presented in three multi-level environments to highlight the search, pursuit and evasion components of the problem.


Toward Simulating Realistic Pursuit-Evasion Using a Roadmap-Based Approach, amuel Rodriguez, Jory Denny, Takis Zourntos, Nancy M. Amato, International Conference on Motion in Games, pp. 82-93, Utrecht, Netherlands, Nov 2010. DOI: https://doi.org/10.1007/978-3-642-16958-8_9
Keywords: Motion Planning
Links : [Published]

BibTex

@inproceedings{rodriguez2010toward,
title={Toward simulating realistic pursuit-evasion using a roadmap-based approach},
author={Rodriguez, Samuel and Denny, Jory and Zourntos, Takis and Amato, Nancy M},
booktitle={International Conference on Motion in Games},
pages={82--93},
year={2010},
organization={Springer}
}


Abstract

In this work, we describe an approach for modeling and simulating group behaviors for pursuit-evasion that uses a graph-based representation of the environment and integrates multi-agent simulation with roadmap-based path planning. We demonstrate the utility of this approach for a variety of scenarios including pursuit-evasion on terrains, in multi-level buildings, and in crowds.


Behavior-Based Evacuation Planning, Samuel Rodriguez, Nancy M. Amato, IEEE International Conference on Robotics and Automation, May 2010. DOI: 10.1109/ROBOT.2010.5509502
Keywords: Group Behavior, Multi-Agent, Sampling-Based Motion Planning
Links : [Published]

BibTex

@inproceedings{rodriguez2010behavior,
title={Behavior-based evacuation planning},
author={Rodriguez, Samuel and Amato, Nancy M},
booktitle={2010 IEEE International Conference on Robotics and Automation},
pages={350--355},
year={2010},
organization={IEEE}
}


Abstract

In this work, we present a formulation of an evacuation planning problem that is inspired by motion planning and describe an integrated behavioral agent-based and roadmap-based motion planning approach to solve it. Our formulation allows users to test the effect on evacuation of a number of different environmental factors. One of our main focuses is to provide a mechanism to investigate how the interaction between agents influences the resulting evacuation plans. Specifically, we explore how various types of control provided by a set of directing agents effects the overall evacuation planning strategies of the evacuating agents.


Shepherding Behaviors, Jyh-Ming Lien, O. Burchan Bayazit, Ross T. Sowell, Samuel Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Vol: 4, pp. 4159-4164, New Orleans, Louisiana, USA, Apr 2004. DOI: 10.1109/ROBOT.2004.1308924
Keywords: Group Behavior, Multi-Agent, Sampling-Based Motion Planning
Links : [Published]

BibTex

@INPROCEEDINGS{1308924,
author={ {Jyh-Ming Lien} and O. B. {Bayazit} and R. T. {Sowell} and S. {Rodriguez} and N. M. {Amato}},
booktitle={IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004}, title={Shepherding behaviors},
year={2004},
volume={4},
number={},
pages={4159-4164 Vol.4},
doi={10.1109/ROBOT.2004.1308924}}


Abstract

Shepherding behaviors are a type of flocking behavior in which outside agents guide or control members of a flock. Shepherding behaviors can be found in various forms in nature. For example, herding, covering, patrolling and collecting are common types of shepherding behaviors. In this work, we investigate ways to simulate these types of behaviors. A shepherd uses roadmaps to steer the flock and to re-group separated flock members. This paper focuses on improving the shepherd's movements to gain better control of the flock's motion and use this improved control to demonstrate a wider variety of shepherding behaviors.


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.


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.