of using abstraction and heuristics is older and was first mentioned under the name ABSTRIPS (Abstraction-Based STRIPS) which was used to efficiently search the state spaces of logic games. A similar technique are navigation meshes (navmesh), which are used for geometrical planning in games and multimodal transportation planning which is utilized in travelling salesman problems with more than one transport vehicle. A map is separated into clusters. On the high-level layer, the path between the clusters is planned. After the plan was found, a second path is planned within a cluster on the lower level. That means, the planning is done in two steps which is a guided local search in the original space. The advantage is, that the number of nodes is smaller and the algorithm performs very well. The disadvantage is, that a hierarchical pathplanner is difficult to implement. Example A map has a size of 3000x2000 nodes. Planning a path on a node base would take very long. Even an efficient algorithm will need to compute many possible graphs. The reason is, that such a map would contain 6 million nodes overall and the possibilities to explore the geometrical space are exceedingly large. The first step for a hierarchical path planner is to divide the map into smaller sub-maps. Each cluster has a size of 300x200 nodes. The number of clusters overall is 10x10=100. In the newly created graph the amount of nodes is small, it is possible to navigate between the 100 clusters, but not within the detailed map. If a valid path was found in the high-level-graph the next step is to plan the path within each cluster. The submap has 300x200 nodes which can be handled by a normal A* pathplanner easily. Algorithms used in pathfinding Dijkstra's algorithm A* search algorithm, a special case of the Dijkstra's algorithm D* a family of incremental heuristic search algorithms for problems in which constraints vary over time or are not completely known when the agent first plans its path Any-angle path planning algorithms, a family of algorithms for planning paths that are not restricted to move along the edges in the search graph, designed to be able to take on any angle and thus find shorter and straighter paths Multi-agent pathfinding Multi-agent pathfinding is to find the paths for multiple agents from their current locations to their target locations without colliding with each other, while at the