Mission Planning for Mobile Robots with Probabilistic Guarantees

Consider an office robot that must execute a range of tasks such as guiding visitors to offices; checking whether fire exits are clear; carrying and delivering items as requested by office users; and making announcements (“staff meeting in 10 minutes!”).

Such guarantees typically include notions such as safety, robustness and efficiency. Safety means robot behaviour must not reach “bad” situations (e.g., colliding with something, driving down steps). Robustness means systems must be able to cope with, and reason about, uncertainties and disturbances during execution. These execution-time variations have different origins, such as the robot’s inaccurate sensors and actuators, or the presence of humans in the environment. Efficiency means the system should strive to optimise a meaningful metric of performance, such as system throughput. These notions can be encoded in high level formalisms, such as temporal logics.

In order to provide probabilistic guarantees over a robot’s mission plans, we have based our approach in an underlying topological map discretisation of the environment. A topological map is drawn over a metric map built by the robot using simultaneous localisation and mapping approaches.

In this topological map, nodes represent possible locations the robot can navigate to, and an edge between two nodes represents that the robot can navigate between them, without visiting any other nodes. Edges can be labelled with different continuous navigation actions that are to be used to navigate between the corresponding nodes. This navigation is monitored by a component that is able to recover from failures by, for example, asking for help.

This simple environmental representation allows us to scale up to large maps and, crucially, to save statistics on whether the robot was able to navigate between certain nodes and how much time the navigation took. Using these statistics, we can learn probabilistic models of the robot’s experiences in the world, and use probabilistic planning approaches to generate behaviour policies. This approach can also be extended to deal with other actions rather than simply navigation, e.g., actions for searching for objects which exploit probabilistic models of object location across the topological map. This extension allows for rich task specifications such as the ones we mentioned in the beginning of this blog.

We have used these techniques in several long term robot deployments, with a combined duration of more than one year of autonomous behaviour. Check out this demo video, which accompanies our recently accepted IJRR paper:

And some examples of our robots wandering around different offices:

If you are interested in learning more about our work, check this overview paper or our tutorial at the 4th Lucia PhD School on “Artificial Intelligence and Robotics, for which we also prepared some practical ROS exercises. There’s also some links for further reading in the end of this blog.

Coming work

We are currently working on extending our work in two different ways: going from service robots to robots in challenging environments such as underwater or nuclear. We are investigating how to to add environmental processes such as underwater currents or radiation components to our probabilistic models. We are also looking into teams of robots, and how to extend our approaches in order to provide fleet level guarantees whilst still being able to scale to tens of robots.

See below a teaser video for our trials at the Fire Service College, where we will do a demo related to radiation-aware monitoring of nuclear environments.

Further reading:

Probabilistic planning with formal performance guarantees for mobile service robots. Bruno Lacerda, Fatma Faruq, David Parker and Nick Hawes. International Journal of Robotics Research (IJRR). 2019.

Optimal and dynamic planning for Markov decision processes with co-safe LTL specifications. Bruno Lacerda, David Parker and Nick Hawes. In Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Chicago, IL, USA, 2014.

Now or later? Predicting and maximising success of navigation actions from long-term experience. Jaime P. Fentanes, Bruno Lacerda, Tomas Krajnik, Nick Hawes and Marc Hanheide. In Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA, 2015.

Optimal Policy Generation for Partially Satisfiable Co-Safe LTL Specifications. Bruno Lacerda, David Parker and Nick Hawes. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), Buenos Aires, Argentina, 2015. 

Nested Value Iteration for Partially Satisfiable Co-Safe LTL Specifications (Extended Abstract). Bruno Lacerda, David Parker and Nick Hawes. In Proceedings of the AAAI Fall Symposium on Sequential Decision Making for Intelligent Agents (SDMIA), Arlington, Virginia, USA, 2015.