When a robot is navigating through an environment crowded by obstacles and other robots, it can get stuck while trying to go from point A to point B. If they get stuck in place, this is often called a deadlock. If they rather get stuck in a pattern of repetitive movements, this is called a livelock. Those locking situations are detrimental to the efficiency of the robot as it loses time and possibly energy. Locking situations should therefore be avoided as much as possible or be recovered from as quickly as possible. Some planning algorithms are more prone to locking situations than others, in particular, decentralised learning-based planners such as DCC, PRIMAL and MAPPER. This is caused by their lack of a mech- anism that explicitly coordinates different agents and their limited perception of the state of the envi- ronment. It would be beneficial if the tendency to get dead- or livelocked could be curbed with simple techniques that can be applied to any planner that works in largely the same manner. Hence, this research proposes and evaluates four methods: punishing actions that lead to an agent getting locked during training (Lock Punishment or LP), training on locking situations encountered during training to teach the model to recover from such a situation (Targeted Training or TT), teach an already trained model to recover from locking situation (Targeted Fine-tuning or TF), and placing obstacles that are only visible to an agent that has just entered a locking situation to encourage it to move away from that location (Phantom Obstacles or PO). All of these methods are evaluated on the same benchmark to see which singular or combination of techniques performs best. In the end, the most effective methods turned out to be PO and a combination of TT and PO. PO demonstrates an increase of 1.6% in its mean success-rate and a decrease of 3% in its computation times over the baseline, and TT+PO’s mean Sum of Costs, Sum of Fuel, and Makespan are lower than the baseline by 0.8%, 1.2% and 2.1% respectively. Although LP+PO has relatively poor performance in most metrics, it reduces the number of locks the baseline encounters by 66%, thus achieving the lowest number of locks.

Path finding is an important component in solving a wide array of engineering problems, ranging from video games to real-life applications such as automated warehouse management and autonomous vehicles.
Path finding algorithms are designed to solve complex problems, and in order to do so, assumptions are necessary to simplify the problems.
While these assumptions are important, using them makes the obtained algorithms less applicable to a real-life scenario, and as such, verifying how lifting some of them would affect the obtained results is worth pursuing.

Two main assumptions were identified and subsequently lifted.
First, classic multi-agent path finding algorithms use a centralized approach, where solutions are computed before execution.
This results in a long computation period followed by execution. Lifting this assumption results in a decentralized approach where agents solve conflicts on the go, while approaching their target.
The second assumption made by state of the art algorithms is that agents participating in a multi-agent path finding problem share a common goal: minimizing a global cost function.
This is not always applicable, as in a real-life scenario participating agents can have selfish goals.
This assumptions has been lifted by allowing agents to negotiate their paths by trading with the other participants to create better solutions for themselves.

The Selfish Localized Pathfinding (SLP) algorithm has been designed to lift these assumptions. It describes a decentralized algorithm that allows participating agents to negotiate their paths, which makes a good candidate for an application closer to real-life.

The SLP algorithm has been tested in order to evaluate its performance, both in terms of its ability to solve a set of test cases, and in terms of the cost incurred by the participating agents.
SLP performed well in varied domains.
SLP solved significantly more cases than Conflict Based Search, a centralized state of the art path finding algorithm.
This comes at the expense of an increase in the path lengths obtained by the algorithm.
This downside is offset by the significant decrease in the time required to solve problems, which can be divided in small clusters due to the decentralized approach of the algorithm.
On the whole, SLP can provide a good alternative to Conflict Based Search.