Multiple agent search of an unknown environment using game theoretical models

This paper addresses the problem of obtaining optimal strategies for searching an unknown environment given in the form of an uncertainty map. Several strategies, in the form of variable length look-ahead policies that depend on the level of communication between searchers are proposed based on Nash equilibrium, security, and cooperative notions in game theory. Simulations are carried out for two searchers on a planar uncertainty map and the performance results are compared with respect to the type of strategies and the length of the look-ahead policies. These simulations show that longer look-ahead policies do not yield better performance than shorter ones, but need high computational effort. The results also show that although communication plays a major role, the performance of Nash and security strategies that do not depend on communication between searchers is comparable with the full-information centralized cooperative case.