Article: Cooperative navigation of unknown environments using potential games Journal: International Journal of Mechatronics and Automation (IJMA) 2014 Vol.4 No.3 pp.173 - 187 Abstract: In this paper, we develop a method of exploring a 2-D environment with multiple robots by modelling the problem as a potential game rather than using conventional frontier-based dynamic programming algorithms. A potential game is a type of game that results in coordinated behaviours amongst players. This is done by enforcing strict rules for each player in selecting an action from its action set. As part of this game, we define a potential function for the game that is meaningful in terms of achieving the greater objective of exploring a space. Furthermore, an objective function is assigned for each player from this potential function. We then create an algorithm for the exploration of an obstacle-filled bounded space, and demonstrate through simulation how it outperforms an uncoordinated algorithm by reducing the time needed to uncover the space. Analysis of the computational complexity of the algorithm will show that the algorithm is of O(sRange²), where sRange is the range of a sensor on a robot. We then suggest an improvement to the proposed algorithm that is premised on having a robot predict the future positions of all other robots. Inderscience Publishers - linking academia, business and industry through research

Title: Cooperative navigation of unknown environments using potential games

Authors: George Philip; Sidney N. Givigi Jr.; Howard M. Schwartz

Addresses: Department of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada ' Department of Electrical and Computer Engineering, Royal Military College of Canada, Kingston, Ontario, Canada ' Department of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada

Abstract: In this paper, we develop a method of exploring a 2-D environment with multiple robots by modelling the problem as a potential game rather than using conventional frontier-based dynamic programming algorithms. A potential game is a type of game that results in coordinated behaviours amongst players. This is done by enforcing strict rules for each player in selecting an action from its action set. As part of this game, we define a potential function for the game that is meaningful in terms of achieving the greater objective of exploring a space. Furthermore, an objective function is assigned for each player from this potential function. We then create an algorithm for the exploration of an obstacle-filled bounded space, and demonstrate through simulation how it outperforms an uncoordinated algorithm by reducing the time needed to uncover the space. Analysis of the computational complexity of the algorithm will show that the algorithm is of O(sRange²), where sRange is the range of a sensor on a robot. We then suggest an improvement to the proposed algorithm that is premised on having a robot predict the future positions of all other robots.

Keywords: weakly acyclic games; potential games; multiple robots; simultaneous localisation and mapping; SLAM; game theory; exploration; modelling; coordinated behaviour; cooperative navigation; robot navigation; multi-robot systems; simulation; robot localisation.

DOI: 10.1504/IJMA.2014.064098

International Journal of Mechatronics and Automation, 2014 Vol.4 No.3, pp.173 - 187

Received: 17 Oct 2013
Accepted: 16 Feb 2014
Published online: 04 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Cooperative navigation of unknown environments using potential games

Keep up-to-date