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 o
...
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.