Abstract

Motion planning is a relevant topic for many modern applications of artificial intelligence like video games, crowd simulation and robotics. In this work we reiterate some fundamental principles of motion planning and pathfinding in order to illuminate some design decisions of existing solutions. An introduction to general artificial intelligence as well as the usage and traversal of graphs is provided so that pathfinding requirements and the following solutions can be discussed more deeply. Some of the most relevant improvements to the field of pathfinding in the recent past are the tessellation of space via navmeshes and the use of hierarchical abstractions. The former is heavily discussed with comparisons to regular grid-like abstractions so that benefits and disadvantages of each specific use case are revealed and put into context. For the latter, we look at two existing hierarchical approaches for grids and navmeshes respectively. While both share some similarities their distinctive underlying geometry lead to fundamentally different solutions. Our approach tries to combine aspects of both solutions and introduces some user guidance to further help optimize pathfinding searches on abstract levels. We additionally introduce a novel idea of a line-graph based heuristic that shall bring insights on the topology of regions and on the behavior of multi-agent systems during the pre-processing phase of our algorithm. This shall avoid heavy calculations during the online search phase and help us fulfill real-time requirements. An implementation of our chosen concepts is provided via the MPHGLT2D framework. While not fully completed at the submission of this work, our approach seems promising to be used in complex multi-agent systems like a Real-Time Strategy game.

Project Description

In this thesis we compare two different kinds of tessellation types, namely regular and irregular tiling. The former can be briefly described as grid-like structures with simple regular polygons as cells, where the later consists of navmeshes with arbitrary complex polygon. Current research suggests to use navmeshes for a more accurate representation of space and that Constrained Delaunay Triangulation (CDT) produces a beneficial search graph, so we opted for this approach as many other modern pathfinding applications commonly use navmesh-based tessellation also.
As research shows, hierarchical abstractions can drastically aid performance improvements of search algorithm on graphs. Our approach with the MPHGLT2D framework tries to combine aspects of previous hierarchical solutions like HPA* (Hierarchical Path-Finding A*) and HNA* (Hierarchical NavMesh Path-finding algorithm). HPA* with its grid based approach is not a perfect fit to provide a solution for our tasks. While HNA* seems to be a better alternative due to the usage of navmeshes, it relies on external tools and does not represent a complete, closed framework. Therefore an attempt to solve these issues is given via MPHGLTD2D. Although our framework does not provide all the desired features yet, it already gives us some insight on hierarchically analysing topologies, which might aid as a multi-agent heuristic in the future.

For performance and scalability reasons, the project itself was implemented with modern C++(20) in mind. Libraries like Boost (1.75) and CGAL (5.2.3) are used as algorithmic support but no further external tools are utilized. Ultimately, integrating the MPHGLT2D framework into a fully developed computer game or crowd simulation to properly illustrate its features and proof its viability would be a successful following step. Due to our heavy considerations of performance and aspirations to support demanding multi-agent environments, we see its adoption in Real Time Strategy games as sensible and beneficial once the framework is fully developed.

Final Presentation