Offline Grid-Based Coverage path planning for guards in games

2020·Arxiv

ABSTRACT

ABSTRACT

Algorithmic approaches to exhaustive coverage have application in video games, enabling automatic game level exploration. Current designs use simple heuristics that frequently result in poor performance or exhibit unnatural behaviour. In this paper, we introduce a novel algorithm for covering a 2D polygonal (with holes) area. We assume prior knowledge of the map layout and use a grid-based world representation. Experimental analysis over several scenarios ranging from simple layouts to more complex maps used in actual games show good performance. This work serves as an initial step towards building a more efficient coverage path planning algorithm for non-player characters.

Keywords Path-planning Coverage More

1 Introduction

Coverage path planning (CPP) is the process of planning a path for an agent that traverses across all areas of a specific location. One of the most challenging aspects of this problem is to optimize the planned path of the agent to cover the area of interest [1]. CPP can be categorized into two types: off-line or online [2]. In off-line coverage, the environment layout is known to the agent, while in on-line coverage the agent has no prior knowledge of the environment. This problem can be approached by several methods. In this paper we use a grid-based approach to implement a novel algorithm to cover an area of interest. Our algorithm is easy to implement, but also guaranteed to solve any area of interest. The algorithm does not guarantee an optimal solution, but it provides the basis for extending the coverage to multiple agents without additional complexity.

In the next section we introduce the related work in the field of coverage path planning, then we describe the methodology of our work. After that, we describe the results the algorithm achieved on selected scenarios. Lastly, we draw our conclusions and future work.

2 Related Work

Coverage path planning has been well studied in the field of robotics for a wide variety of applications, such as vacuum cleaning robots [3], lawnmowers [4], unmanned aerial vehicle (UAV) surveillance [5], etc. The literature includes several methods for CPP, but the methods heavily depend on the representation of the space, either relying on continuous space representations, such as using convexity, or on discrete, grid-based models.

Convex Decomposition decomposes the traversable space into simple, non-overlapping convex regions. After the decomposition, solving the problem of coverage path planning relies on finding the shortest path to visit these regions along with the coverage pattern for each region. Examples of appropriate coverage patterns are zigzag [6], spiral [7]. Once the space has been decomposed into convex sub-regions, an adjacency graph can be used to represent the decomposed space. In the graph, the nodes are the convex regions and the edges between the nodes represent the adjacency between the convex regions. The agent uses this graph to plan the shortest path to traverse all convex regions and recursively the shortest coverage pattern for each region.

Grid-Based approaches decompose the space into a grid of uniformly distributed nodes [8]. Each node can be traversable or non-traversable. In this representation, CPP is accomplished by traversing all reachable nodes, associating either a binary or probabilistic [9] property to coverage. Grid-based methods are resolution-dependent, and their completeness relies on the granularity of the grid. Grid-based representation is one of the simplest methods to use. However, for larger spaces, this method becomes computationally expensive compared to other methods [10].

3 Methodology

In this section, we describe the space representation method chosen for our algorithm. After that, we explain how our algorithm accomplishes coverage path planning to an area of interest.

3.1 Space Representation

For our method, we use a 2D grid-based representation; The space is discretized into a grid of nodes, and each node has three possible states: untraversable, seen and unseen. The grid connectivity is based on von Neumann neighborhood where the agent moves by taking a step to the adjacent nodes in four directions; up, down, left and right. The agent’s field of view is represented by a cone with a limited range and angle; other FoV models are also possible. Once an unseen node falls within the vision cone that node becomes seen. The condition to consider a scenario to be successfully finished is when all the traversable nodes are seen. Figure 1 shows an example of the simulation.

Figure 1: An example of the simulation. The map is taken from the game “Metal Gear Solid”. The darkest nodes are unseen traversable nodes. Once an unseen node is seen it becomes transparent. The lighter nodes are untraversable. The number on the center indicates the percentage of unseen nodes.

3.2 RippleFront Algorithm

For our approach, we based our implementation on the WaveFront coverage algorithm [11]. We refer to it as the “RippleFront algorithm.” It works by propagating the distance from the unseen nodes through the seen nodes. The propagation procedure is constantly executed every fixed time interval.

Algorithm 1 shows the pseudo-code for the RippleFront where N is the list of nodes in the grid, D(n) is the Manhattan distance to the closest unseen node. At every iteration, D(n) is updated by assigning the Min(D(l)) where l is an adjacent to n. D(n) value will be updated by adding the value of , where is the neighbor node with the shortest distance from the closest unseen node. The added 1 is the step cost from n to .

The RippleFront focuses on creating an overall road map that makes it trivial for the agent to decide the direction of its next step to discover unseen locations. However, the coverage path is not guaranteed to be optimal due to the greedy decision process the agent adopts, which is simply to face and step towards the node closest to an unseen node. Nevertheless, this approach provides a guarantee to solve the map.

4 Results

We ran our simulation using Unity3D game engine 1. We tested the algorithm on 4 scenarios with different complexities. Figure 2 shows the layout of the maps used for our simulations. The maps have different complexities but they all have the same grid size.

Figure 2: Maps used for the simulation.

To measure the agent’s performance, we used the number of steps the agent required to cover a map. The length of a step is the distance between two adjacent nodes, vertically or horizontally. To assess the overall performance, We logged the total steps the agent took for each episode and ran 200 episodes for each scenario. For every episode the agent had a random starting position and tasked with covering the overall map. Figure 3 shows the performance of our algorithm on the 4 scenarios. While all scenarios have the same grid size, each scenario has a different number of traversable nodes. This led to the difference in performance between these scenarios.

Figure 3: The performance for 200 episodes for each of the 4 scenarios.

5 Conclusions & Future work

In this paper, we introduced a novel offline grid-based algorithm for coverage path planning. Our algorithm is simple to implement and guaranteed to solve any scenario. This is of course preliminary work. Our future goals include conducting performance comparisons with other, existing algorithms or heuristics, considering computation time as well as number of steps. We are also interested in extending the design to the context of multiple agents, where communicating agents cooperate to perform concurrent coverage.

6 Acknowledgement

This work was supported by the Natural Science and Engi-neering Research Council of Canada, Computing Hardware for Emerging Intelligent Sensing Applications (COHESA).

References

[1] Chung-Hsien Kuo, Hung-Chyun Chou, and Sheng-Yu Tasi. Pneumatic sensor: A complete coverage improvement approach for robotic cleaners. IEEE Transactions on Instrumentation and Measurement, 60(4):1237–1256, 2011.

[2] Howie Choset. Coverage for robotics–a survey of recent results. Annals of mathematics and artificial intelligence, 31(1-4):113–126, 2001.

[3] Fumio Yasutomi, Makoto Yamada, and Kazuyoshi Tsukamoto. Cleaning robot control. In Proceedings. 1988 IEEE International Conference on Robotics and Automation, pages 1839–1841. IEEE, 1988.

[4] Zuo Llang Cao, Yuyu Huang, and Ernest L Hall. Region filling operations with random obstacle avoidance for mobile robots. Journal of Robotic systems, 5(2):87–102, 1988.

[5] Nicola Basilico and Stefano Carpin. Deploying teams of heterogeneous uavs in cooperative two-level surveil- lance missions. In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 610–615. IEEE, 2015.

[6] Howie Choset and Philippe Pignon. Coverage path planning: The boustrophedon cellular decomposition. In Field and service robotics, pages 203–209. Springer, 1998.

[7] Fotios Balampanis, Ivan Maza, and Anibal Ollero. Spiral-like coverage path planning for multiple heterogeneous uas operating in coastal regions. In 2017 International Conference on Unmanned Aircraft Systems (ICUAS), pages 617–624. IEEE, 2017.

[8] Hans Moravec and Alberto Elfes. High resolution maps from wide angle sonar. In Proceedings. 1985 IEEE International Conference on Robotics and Automation, volume 2, pages 116–121. IEEE, 1985.

[9] Alberto Elfes. Sonar-based real-world mapping and navigation. IEEE Journal on Robotics and Automation, 3(3):249–265, 1987.

[10] Sebastian Thrun. Learning metric-topological maps for indoor mobile robot navigation. Artificial Intelligence, 99(1):21–71, 1998.

[11] Vikas Shivashankar, Rajiv Jain, Ugur Kuter, and Dana Nau. Real-time planning for covering an initially-unknown spatial environment. In Twenty-Fourth International FLAIRS Conference, 2011.