Multi-agent simulation with market-based task allocation of survivor rescues in emergency situations.
The project will be implemented by Are Oelsner and Calvin Bauer, and will simulate a robotic rescue operation. In the aftermath of a chemical plant collapse, clusters of survivors are stuck in the debris, and their time to breathe safely is running out. Multiple robots that have varying numbers of gas masks (which will save one survivor each) are placed around the space, and they need to coordinate to plan delivery of the maximum number of masks to the most people before time runs out. The world will first be split into a discrete grid with obstacles, to simplify the path planning element of the problem. Each robot and cluster of survivors will be represented as a point in space, based on the assumption that the obstacle regions have already been defined to not allow the robots too close to a real obstacle. The coordination process will be executed as a market-based approach, inspired by [1]. Each robot will calculate its path to each group of survivors, and submit a “bid” to a central planner consisting of how many people would be saved, and how long it would take for the robot to get there. The planner is then responsible for assigning each robot to one of its bids, with the goal of saving the highest total number of people possible. There are multiple opportunities to extend the scope of this project and explore the problem more deeply. Once the implementation of the discrete world is complete, we intend to analyze how our solution could apply to a continuous space. Chapter 5 of [2] goes into detail on sampling approaches that would apply to our robot. We hope to implement a simple translation of our world from discrete to continuous space by approximating the space as a grid, an approach discussed by Lavalle. If that transition can be made, we may look at other approaches to continuous space, such as RRT ([3]) or a combinatorial roadmap ([2], chapter 6). Another interesting facet of this problem is the way the central planner assigns paths, which is covered more deeply in [4]. We plan to analyze how the problem would scale to massive environments with thousands of robots and survivors, and discuss the kinds of optimizations that would be needed for the solution to remain practical.
This project will be feasible primarily for two reasons. First, Are has experience building multi-agent simulations, while Calvin has experience with path planning in grid-based environments. Constructing the environment and calculating a path for each robot will be a significant part of the overall effort, and our prior expertise will be highly beneficial. Second, we have set our base goals and schedule conservatively, to account for unexpected challenges that may arise in the implementation. If we can accomplish our initial goals without significant hurdles, we will be able to move on to more intricate facets of the problem, as mentioned above.
We aim to finalize which simulator we will be using by October 14th. We are currently considering Gazebo, Unity, and making a simple simulator in python, among other options. From there, our first major milestone, due October 24th, will be setting up a basic simulation environment: creating a simple 2D grid environment in our simulator with a single agent navigating to a goal location. Our second major milestone, due on November 9th, will be implementing our bid system and simple central planner, with optimal path planning in a discrete space with no obstacles and varying mask amounts. In this simple space, agents will submit bids for different groups of survivors, and our planner will assign tasks such that the most lives are saved within the time constraint. Agents will then navigate to their goals and distribute masks to survivors with optimal path planning. Our third milestone, due on November 23rd, will be adding obstacles, A* search path planning, and refining our bidding system and central planner. Implementing these steps fulfills our base success condition for the project. With the previous milestones achieved, we hope to go beyond our base success criteria and extend our project to operate in continuous space abstracted into a grid with obstacles approximated as collections of grid cells. We hope to have this accomplished by December 9th if possible. Our stretch goals are to switch from our grid search navigation to a RRT or roadmap based approach, and to allow one robot to visit multiple groups. At the end of the project, regardless of whether we were able to implement a continuous solution, we will analyze real-world applications of our implementation, along with potential adjustments to improve scalability and flexibility.
The success criteria for this project will be twofold. First, we must at least complete our third milestone: implementing our bidding system and central planner in a discrete 2D environment with obstacles such that agents are allocated tasks in a way that maximizes lives saved within the time constraints. In order to fully accomplish the third milestone we will need to set up a simulation environment and a grid based navigation system within that environment, including a market-based task assignment algorithm that will handle auctions and allocation of tasks to agents. Second, we will need to examine the real world application of the problem, and how our solution would need to be adjusted for continuous space.
The primary reason we decided to work together on the project is that the problem offers a rich problem space that we want to explore as deeply as possible. There will be a significant amount of work in setting up the environment with multiple agents, as well as algorithm design to coordinate the agents. We will both work on building the environment and creating the algorithms, and will create a git repository to coordinate our progress. With her background in simulations, Are will focus more on creating the simulation environment, while Calvin’s experience in grid path planning algorithms will allow him to spearhead the algorithm implementation. Though we hope to partition the responsibilities as much as possible, we both expect to be closely involved in all aspects of the project.
[1] Dias, M.B., et al. “Market-Based Multirobot Coordination: A Survey and Analysis.” Proceedings of the IEEE, vol. 94, no. 7, 2006, pp. 1257–1270., https://doi.org/10.1109/jproc.2006.876939.
[2] LaValle, Steven Michael. Planning Algorithms. Cambridge University Press, 2014.
[3] LaValle, S.M., and J.J. Kuffner. “Randomized Kinodynamic Planning.” Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C), https://doi.org/10.1109/robot.1999.770022.
[4] Kuhn, H. W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics, vol. 52, no. 1, 2005, pp. 7–21., https://doi.org/10.1002/nav.20053.