Robotic adversarial coverage of known environments
| Autor: | Gal A. Kaminka, Roi Yehoshua, Noa Agmon |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
0209 industrial biotechnology
Engineering 02 engineering and technology Computer security computer.software_genre Adversarial system 020901 industrial engineering & automation Artificial Intelligence 0202 electrical engineering electronic engineering information engineering Point (geometry) Motion planning Electrical and Electronic Engineering business.industry Applied Mathematics Mechanical Engineering Robotics Industrial engineering Demining Work (electrical) Modeling and Simulation Robot 020201 artificial intelligence & image processing Artificial intelligence business computer Software |
| Zdroj: | The International Journal of Robotics Research. 35:1419-1444 |
| ISSN: | 1741-3176 0278-3649 |
| DOI: | 10.1177/0278364915625785 |
| Popis: | Coverage is a fundamental problem in robotics, where one or more robots are required to visit each point in a target area at least once. Most previous work has concentrated on finding a coverage path that would minimize the coverage time. In this paper, we consider a new and more general version of the problem: adversarial coverage. Here, the robot operates in an environment that contains threats that might stop the robot. The objective is to cover the target area as quickly as possible, while minimizing the probability that the robot will be stopped before completing the coverage. This version of the problem has many real-world applications, from performing coverage missions in hazardous fields such as nuclear power plants, to surveillance of enemy forces in the battlefield and field demining. In this paper, we discuss the offline version of adversarial coverage, in which a map of the threats is given to the robot in advance. First, we formally define the adversarial coverage problem and present different optimization criteria used to evaluate coverage algorithms in adversarial environments. We show that finding an optimal solution to the adversarial coverage problem is [Formula: see text]-hard. We therefore suggest two heuristic algorithms: STAC, a spanning-tree-based coverage algorithm, and GAC, which follows a greedy approach. We establish theoretical bounds on the total risk involved in the coverage paths created by these algorithms and on their lengths. Lastly, we compare the effectiveness of these two algorithms in various environments and settings. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|