T owards Safest Path Adversarial Coverage (Extended Abstract)
Roi Yehoshua, Noa Agmon, Gal A. Kaminka · 2014
Coverage is a fundamental problem in robotics, where a robot is required to visit every part of a given area as efficiently as possible ([1], [3], [4], [5], [6], [8]). Coverage has many applications in various domains, from automatic floor cleaning to humanitarian missions such as search and rescue and field demining. The coverage problem is analogous to the traveling salesman problem (TSP), which is known to be NP-complete [1]. However, it is possible to find solutions to the coverage problem that are close to optimal in polynomial or even linear time through heuristics and reductions (e.g., [1], [3], [5], [8]). Almost all previous studies of the coverage problem dealt with non-adversarial settings, where nothing in the environment is hindering the robot’s task. However, in many occasions, robots and autonomous agents need to perform coverage missions in hazardous environments, such as operations in nuclear power plants, exploration of Mars, demining and surveillance of enemy forces in the battle field. In the adversarial coverage problem [9], the target area contains locations with potential threats of harming the robot, in addition to obstacles which the robot cannot go through. The robot’s task is to cover the entire target area as quickly as possible without being damaged by a threat point. In the offline version of this problem, a map with the locations of the potential threats is given in advance, therefore the