Planning for Multiple Robots in Congested Environments

Home/GOALS, ORI Blog, yr_2020/Planning for Multiple Robots in Congested Environments
Charlie Street
Charlie StreetDPhil Student

Planning for Multiple Robots in Congested Environments

When most of us plan journeys, chances are at some point we open Google Maps to find an array of colours telling us that we will probably experience traffic at certain points on our journey. This allows us to plan our journeys accordingly, possibly choosing to take a longer route with less traffic.

This begs the question: If we can plan our journeys to avoid congested areas, why can’t robots?

This blog post provides an overview of our recent paper ‘Multi-Robot Planning Under Uncertainty with Congestion-Aware Models’ which addresses this problem:

  • [PDF] C. Street, B. Lacerda, M. Mühlig, and N. Hawes, “Multi-Robot Planning Under Uncertainty with Congestion-Aware Models,” in 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Auckland, New Zealand, 2020.
    [Bibtex]
    @inproceedings{2020AAMAS_street,
    title={Multi-Robot Planning Under Uncertainty with Congestion-Aware Models},
    author={Street, Charlie and Lacerda, Bruno and Mühlig, Manuel and Hawes, Nick},
    booktitle={19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)},
    address={Auckland, New Zealand},
    month = {May},
    year = {2020},
    organization={IFAAMAS},
    pdf={http://www.robots.ox.ac.uk/~mobile/Papers/2020AAMAS_street.pdf},
    }

What do we want to do?

Multi-robot systems are now deployed widely in warehouse logistics, agriculture and on our roads. Commonly, we wish to solve multi-robot path planning problems in these environments, where each robot has a goal location to reach, and robots should not collide. However, these environments contain areas that suffer from congestion, i.e. if multiple robots are present simultaneously, they have to slow down in order to manoeuvre around each other.

For example, see the below video. In this mock warehouse, robots are slowed down when they meet in the tunnels:

There are two common approaches for handling these environments: either robots are blocked from being in the same area at the same time, which results in robots having to wait for long periods, or robots have no awareness of congestion, and so are slowed down significantly when it occurs.

We want to provide a middle ground between the two approaches I’ve described above, and so we solve multi-robot path planning problems in these congested environments by explicitly reasoning about the effect of congestion on the robots. By doing this, a robot may take a longer, less congested route instead of a shorter, congested route if it can reach its goal faster.

What are the challenges?

  • Planning for multiple robots is complex: Planning for single robots can prove to be computationally expensive, as we may have to consider many factors of the environment in order to plan effectively, such as the locations of objects, whether doors are open/closed etc. When we add multiple robots to the environment, planning becomes even more expensive, exponentially so in the worst case.
  • We live in a continuous and uncertain world: Many works on multi-robot planning assume the world behaves in a deterministic way. This doesn’t hold in reality, e.g. if a robot navigates between two points, the time it will take comes from a continuous range of values, and every time the robot navigates, this time will be different.
  • We need to make the robots aware of each other: To reduce the complexity of planning for multiple robots, we often choose to plan for each robot separately. As a result of this, we need to make the robots aware of what the others are planning to do.

Our Solution

In order to effectively reason about congestion, we need to answer two questions:

  1. How do we model the duration of navigation actions?
  2. Where is a robot most likely to be at a particular time?

To answer question 1, recall that we live in a continuous and uncertain world, and so if a robot navigates between two points, it will take an uncertain amount of continuous time. Our solution is to model this duration using a continuous probability distribution. In particular, we represent our environment as a topological map, which is a set of nodes and edges between them. An example of such a map for a mock warehouse can be seen below, where nodes are octagons and edges are the lines between them:

We then build distributions for each of these edges. However, we also need to model the effect congestion has on this duration. Therefore, we have a distribution for each edge and for each number of robots that may be alongside a robot on that edge. These distributions may look like the ones below:

Note how as the number of robots increases, these distributions shift to the right and flatten out. This means that the more robots present on an edge, the longer it takes to navigate through it, and the more uncertain we become about this duration.

By combining these distributions together over a robot’s route, we can predict where a robot will be at a given time. If we can do this for every robot, we can estimate the level of congestion across the map. Predictions over the level of congestion can then be used to inform robots about the location of the other robots during planning.

In the video below, we demonstrate our model of congestion. With 5 robots moving through the environment, we show our model’s prediction of how congested the environment will be. The graph on the right shows how our predictions of the number of robots on the middle tunnel edge evolve over time.

How does this approach perform?

We carried out experiments to test the scalability of our planning framework, as well as the effectiveness of our generated plans.

When testing the scalability, we found that our framework can scale up to 15 robots, a large number when planning in uncertain environments. A sample of our results when testing in a small warehouse map can be seen below:

To test how well our framework routes our robots through the environment, we compared against a method that prevents robots being present in the same area at the same time, which mirrors existing approaches to the problem. In this experiment we measured the time until the last robot reaches its goal (the makespan) for both of these methods, and found that our framework produces lower times, as it more effectively distributes the robots across the environment.

What’s next?

Our directions for future research include:

  • Verifying the behaviour of our robots, e.g. what is the probability our robots complete their task within 5 minutes?
  • Planning for robots to meet and collaborate, while minimising how long the robots remain idle waiting.
  • Removing assumptions from our current framework to develop better planning solutions.

Further reading

If you’ve found yourself interested in what I’ve discussed here, I recommend the following works:

  • Claes, D., Robbel, P., Oliehoek, F.A., Hennes, D., Tuyls, K. and Van der Hoek, W., 2015. Effective approximations for multi-robot coordination in spatially distributed tasks. In Proceedings of the Fourteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (pp. 881-890).
  • Zhang, S., Jiang, Y., Sharon, G. and Stone, P., 2017. Multirobot Symbolic Planning under Temporal Uncertainty. In Proceedings of the Sixteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (pp. 501-510).
  • D. Silver, 2005. Cooperative pathfinding. In Proceedings of the first AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE) (pp. 117–122).

Contact us

For any questions feel free to email me: cstreet at robots.ox.ac.uk

To keep up to date on our research, follow @GOALS_oxford on Twitter!

By |2020-03-09T10:45:50+00:00March 9th, 2020|GOALS, ORI Blog, yr_2020|Comments Off on Planning for Multiple Robots in Congested Environments