A significant body of work exists on effectively allowing multiple agents to coordinate to achieve a shared goal. In particular, a growing body of work in the Distributed
Constraint Optimization (DCOP) framework enables such coordination with different
amounts of teamwork. Such algorithms can implicitly or explicitly trade-off improved
solution quality with increased communication and computation requirements. However, the DCOP framework is limited to planning problems; DCOP agents must have
complete and accurate knowledge about the reward function at plan time.
We extend the DCOP framework, defining the Distributed Coordination of Exploration and Exploitation (DCEE) problem class to address real-world problems, such as
ad-hoc wireless network optimization, via multiple novel algorithms. DCEE algorithms
differ from DCOP algorithms in that they (1) are limited to a finite number of actions
in a single trial, (2) attempt to maximize the on-line, rather than final, reward, (3) are
unable to exhaustively explore all possible actions, and (4) may have knowledge about
the distribution of rewards in the environment, but not the rewards themselves. Thus, a
DCEE problem is not a type of planning problem, as DCEE algorithms must carefully
balance and coordinate multiple agents’ exploration and exploitation.
Two classes of algorithms are introduced: static estimation algorithms perform simple calculations that allow agents to either stay or explore, and balanced exploration
algorithms use knowledge about the distribution of the rewards and the time remaining
in an experiment to decide whether to stay, explore, or (in some algorithms) backtrack to
a previous location. These two classes of DCEE algorithms are compared in simulation
and on physical robots in a complex mobile ad-hoc wireless network setting. Contrary to our expectations, we found that increasing teamwork in DCEE algorithms may lower
team performance. In contrast, agents running DCOP algorithms improve their reward
as teamwork increases. We term this previously unknown phenomenon the team uncertainty penalty, analyze it in both simulation and on robots, and present techniques to
ameliorate the penalty.