Enhancing Scale and Performance of Safe and Trusted Multi-Agent Planning

Cooperative Multi-Agent Planning (MAP) is a topic in symbolic artificial intelligence (AI). In a cooperative MAP system, multiple agents collaborate to achieve a common goal. A cooperative MAP solver produces human-understandable action sequences that solve a given problem, allowing increase in trustworthiness of the AI system. Specifically, since the solutions are human-understandable, users can verify their correctness and ensure safety in collaborating with AI-controlled entities. Applications of cooperative MAP include electrical grid optimisation and multi-robot navigation.

However, the application of cooperative MAP is limited by its high computational cost. Hardware acceleration is a promising approach to scale up cooperative MAP solvers, allowing them to cope with practical problems. In particular, graphics processing units (GPUs) and field-programmable gate arrays (FPGAs) can be used to speed up computationally expensive routines. Although hardware acceleration has achieved success in many fields of AI such as deep learning, its application to cooperative MAP is not well studied. For instance, all the 23 state-of-the-art MAP solvers discussed in [Ale17] run on CPU-based platforms.

The proposed approach would be particularly useful for time-critical safety-related tasks, since it allows MAP solvers to cope with crowded environments with high performance. For example, [Baj19] introduces a technique for navigating multiple robots in an environment without colliding with walking people or with other robots. However, the current CPU-based MAP solver can only compute safe paths in real-time for 5 robots, while many real systems are much larger: the Quiet Logistic Centre (QLC) in Massachusetts, USA has 200 autonomous pick-and-place robots collaborating with human employees [Li16] to arrange parcels. From the performance model in [Baj19], a 40-fold speedup would allow real-time safe path planning for the 200 robots in QLC. The proposed acceleration will enable such speedup to make large-scale safe planning a reality.

This research project concerns contributing to safe and trusted MAP solvers by enhancing their capability and performance. It involves four themes:
(i) the adaptation of software MAP algorithms to facilitate hardware acceleration;
(ii) the design, optimisation and evaluation of hardware accelerators based on the adapted algorithms using GPUs and/or FPGAs;
(iii) a case study on a human-in-the-loop MAP problem involving multi-agent multi-human safe path planning [Baj19];
(iv) a new approach based on accelerated MAP solvers for real-time safe and trusted path planning with increased scale and performance.

[Baj19] Bajcsy, Andrea, et al. “A scalable framework for real-time multi-robot, multi-human collision avoidance.” International conference on robotics and automation. IEEE, 2019.

[Tor17] Torreño, Alejandro, et al. “Cooperative multi-agent planning: A survey.” ACM Computing Surveys, 50.6 (2017): 1-32.

[Li16] Li, Jun-tao, and Hong-jian Liu. “Design optimisation of amazon robotics.” Automation, Control and Intelligent Systems 4.2 (2016): 48-52.

Project ID



Wayne Lukhttps://www.doc.ic.ac.uk/~wl/


AI Planning