A Clustering Approach to Path Planning for Big Groups

Introduction

The path planning or more specifically the task of finding a path between two or more spots in some environment is an important research problem, useful in many different applications, e.g., in robotics, molecular biology or simulations of crowds. The environment can be static or dynamic and is represented by a graph of vertices and edges. In the dynamic environment, the environment properties or its topology may change over time. The static environment does not allow any changes. The paths are planned for entities, which are often called agents.

While the path planning for one agent in the static environment can be considered as a solved problem, the situation is different for more agents or even huge groups in a dynamic environment: a repeated recomputation of path for many changes and many agents may be too slow. For a huge number of agents, the optimality of the paths is less important than the speed of computation as the application for this version of path planning problem usually rather needs the crowd to look well and realistic than to compute and use optimal paths. A similar problem is currently in molecular biology where water molecules have to be navigated through proteins. Therefore, there is a research space for algorithms, sacrificing optimality to speed.

We proposed an algorithm that takes advantage of path similarity of some agents (Szkandera, Kolingerová, & Maňák, 2017). The agents are grouped according to their initial and target position and the path is found only once for the whole group. The method brought a speed-up and memory savings but there was still space for an improvement. Later (Szkandera, Kaas, & Kolingerová, 2017) we proposed to incorporate a more sophisticated approach of groups formation based on clustering. In this way it is possible to increase the speed-up without fatal consequences on the relative error of the produced paths.

The algorithm proposed here is a generalized version of the clustering-based solution, enabling to include also new-coming agents.

This paper is organized as follows. Section Related Work outlines existing path planning methods, which are suitable for the simulation of big groups, and clustering methods. Section Proposed Solution describes the new algorithm. Section Experiments and Results contains the results of experiments performed on real environment data, e.g. town and molecular environments, and a comparison to classic path planning approach. Section Conclusion concludes the paper.