Page 72 - Innovations in Intelligent Machines

Team, Game, and Negotiation based UAV Task Allocation 61
5 Search using Game Theoretic Strategies

In the previous section we have seen search task to be a part of other tasks
to be carried out by the UAVs. However, there are applications like search
and surveillance missions where search is the only task that has to be carried
out. By search we mean that the UAVs are deployed in an unknown region to
collect information about the region.
Consider an unknown region over which a search mission has to be carried
out. Based on the a priori knowledge of the search space, an uncertainty
map is constructed. The uncertainty map is discretized into cells. Here, we
discretize the map into a grid of hexagonal cells, as they offer the flexibility
to move in any direction while expending the same amount of energy. The
uncertainty map constitutes real numbers between 0 and 1 associated with
each cell in the search space. These numbers represent the uncertainty with
which the location of the target is known in that cell. An uncertainty value of
0 would imply that everything is known about the cell (that is, one can say
with certainty whether a target is located in that cell or not). On the other
hand, an uncertainty value of 1 would imply that nothing can be said about
the location of the target in that cell.
One of the motivations for modeling a search problem in a game theore-
tical framework arises from the fact that this framework gives the flexibility
of using two different solution concepts: one based on cooperation between
players and the other based upon non-cooperation. Application of these
notions to the economics had to take into account the fact that players are
not inherently altruistic, thus making the cooperative framework somewhat
untenable, unless the cooperation is enforced by a third party. On the other
hand, in the non-cooperative framework it has been shown that in repeated
games, cooperation automatically emerges as the best noncooperative solu-
tion and hence the notion of cooperation is inherent and enforceable in the
non-cooperative framework. Although when we consider cooperation between
automated agents that are devoid of any selfish motive and have only a com-
mon goal in mind, it is more logical to use a cooperative framework, in our
work we show that the non-cooperative framework is almost equally effective
and is no more computationally time consuming than the cooperative frame-
work. There are other reasons too, related to the specific problem structure,
which justifies the usage of the non-cooperative framework. For instance, when
the sensor performance is unreliable or noisy, or due to ineffective communica-
tion the uncertainty map of each agent changes with time unknowingly to the
other agents, leading to different uncertainty map for different agents. In such
situations, the cooperative decision making mechanism breaks down. Here we
show that when this is the case, the non-cooperative Nash strategies perform
better than the cooperative strategies.