Home // ADAPTIVE 2013, The Fifth International Conference on Adaptive and Self-Adaptive Systems and Applications // View article

StaCo: Stackelberg-based Coverage Approach in Robotic Swarms

Authors:
Katerina Stankova
Bijan Ranjbar-Sahraei
Gerhard Weiss
Karl Tuyls

Keywords: Swarm robots; Coverage control; Lloyd algorithm; Game theory; Stackelberg games

Abstract:
The Lloyd algorithm is a key concept in multi-robot Voronoi coverage applications. Its advantages are its simplicity of implementation and asymptotic convergence to the robots' optimal position. However, the speed of this convergence cannot be guaranteed and therefore reaching the optimal position may be very slow. Moreover, in order to ensure the convergence, the Hessian of the corresponding cost function has to be positive definite all the time. Validation of this condition is mostly impossible and, as a consequence, for some problems the standard approach fails and leads to a non-optimal positioning. In such situations more advanced optimization tools have to be adopted. This paper introduces Stackelberg games as such a tool. The key assumption is that at least one robot can predict short-term behavior of other robots. We introduce the Stackelberg games, apply them to the multi-robot coverage problem, and show both theoretically and by means of case studies how the Stackelberg-based coverage approach outperforms the standard Lloyd algorithm.

Pages: 71 to 76

Copyright: Copyright (c) IARIA, 2013

Publication date: May 27, 2013

Published in: conference

ISSN: 2308-4146

ISBN: 978-1-61208-274-5

Location: Valencia, Spain

Dates: from May 27, 2013 to June 1, 2013