Multi-robot systems provide great benefits in applications such as coordinated search and rescue, large scale agriculture, and efficient transportation of people and goods. When a group of mobile robots operate in shared space coordination between them is crucial. In particular, strategies for task assignment and collision avoidance are needed. Task assignment is the problem of determining which robot moves to which desired position. It can be written as a combinatorial optimisation problem with the objective of minimising a function that depends on the costs of moving the individual robots to their assigned destinations. Examples of different cost functions considered are the sum of the assigned travel distances (linear sum assignment problem) or the maximum assigned travel distance (bottleneck assignment problem). Collision avoidance captures the requirement of robots having to keep a safe distance from each other. Many different approaches for avoiding collisions exist in the robotics literature. In this project, the focus is on exploiting properties of an optimal robot-task assignment to guarantee that robots do not collide.
The aim of the work is to compare and extend different existing approaches to the robot-goal allocation that provide guarantees for collision-free trajectories. Specific problems that are left open by the existing literature include the analysis of the effect of considering only subsets of goals and robots for the assignment and the quantification of the amount of deviation from a straight-line path that can be tolerated when goals are allocated with a linear sum assignment. These problems can be addressed by conducting extensive case studies and applying the recent advancements in the theory of assignment sensitivity. The methods will be compared based on their properties, e.g., the property of a re-assignment that is determined once the robots are en route remaining the same as the initial optimal assignment (dynamic consistency) and the property of being able to distribute the computation required to obtain the optimal assignment across the robots (distributability) as well as the required assumptions, e.g., robots travel with constant velocity or in straight lines. The project will consist of theoretical research and algorithm development. A simulation environment will be created to test the resulting path-planning methods.
Requirements and key learnings:
The student is required to have a good knowledge of optimisation methods and some basic programming skills (C++ or Python). Experience with Gazebo and ROS is beneficial. In this project, the student will learn about task assignment problems, graph-based optimisation, sensitivity analysis, distributed algorithms, and multi-robot coordination.
This project can be taken as a master project (PDM) by extending it to include the investigation of task assignment problems where agents can complete more than one task (generalised assignment problems).
Background reading:
->https://journals.sagepub.com/doi/full/10.1177/0278364913515307,
->https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/viewPaper/10006,
->https://ieeexplore.ieee.org/abstract/document/9140307.
Interested students should contact Tony Wood.