Stackelberg-based Coverage Approach in Nonconvex Environments
Bijan Ranjbar-Sahraei, Kateřina Staňková, Karl Tuyls, Gerhard Weiß · 2013
This paper introduces StaCo: Stackelberg-based Coverage approach for nonconvex environments. This approach struc-turally differs from existing methods to cover a nonconvex environment, as it is based on a game-theoretic concept of Stackelberg games. Our key assumption is that one robot can predict (short-term) behavior of other robots. No direct com-munication takes place among the robots, the approach is de-centralized. However, the leading robot can direct the system into the optimal setting much more efficiently just by chang-ing its own position. This paper extends our previous work in which we have introduced the StaCo approach for coverage of a convex environment, with a simpler type of robots. We pro-vide theoretical foundations of the approach. We demonstrate its benefits by means of case studies (using the Sim.I.am soft-ware). We show situations in which the StaCo approach out-performs the standard approach, which is based on combina-tion of the Lloyd algorithm and path planning.