A Clustering Approach to Path Planning for Big Groups

A Clustering Approach to Path Planning for Big Groups

Jakub Szkandera (University of West Bohemia, Pilsen, Czech Republic), Ondřej Kaas (University of West Bohemia, Pilsen, Czech Republic) and Ivana Kolingerová (University of West Bohemia, Pilsen, Czech Republic)
Copyright: © 2019 |Pages: 20
DOI: 10.4018/IJDWM.2019040103

Abstract

The article introduces a new method of planning paths for big groups in dynamic environments represented by a graph of vertices and edges, where the edge weight as well as the graph topology may change, but the method is also applicable to environments with a different representation. The utilization of clustering enables the use of a computed path for a group of agents. In this way, a speed-up and memory savings are achieved at a cost of some path sub-optimality. Examples of proper applications of the suggested approach are crowd simulation in urban environments or path-planning-based tasks in molecular biology. The experiments showed good behaviour of the method to speed-up, relative error and online computation.
Article Preview
Top

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 17: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 16: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing