Search

General Game Playing with Incomplete Information (GGP-II) is about developing a system capable of successfully playing incomplete information games without human intervention by just receiving their rules at runtime. Different algorithms (players) have been provided to play games in GGP-II. This research is concerned with three main limitations of algorithms in the literature: valuing-information, generating mixed strategy and cooperating in games which require implicit communication. In this thesis, I theoretically and experimentally show why past GGP-II players suffer from these problems and introduce four algorithms to overcome these problems and discuss the advantages and limitations of each algorithm. Firstly, I introduce the Iterative Tree Search (ITS) algorithm. ITS learns the best strategy by simulating different plays with itself. I show theoretically and experimentally how ITS correctly values information and models opponents by generating mixed strategies in different games. However, ITS fails to play large games and also the cooperative games which require implicit communication. Secondly, I present the Monte Carlo Iterative Tree Search (MCITS). This algorithm uses Monte Carlo Tree Search technique to focus the search on a more promising part of the game. I experimentally show the success of this algorithm on different games from the literature. MCITS fails to generate mixed strategies and to correctly play games which require implicit communication. Thirdly, I introduce a communication language learning technique called General Language (GL). GL is capable of generating an implicit communication language for cooperative players to share their information. The GL technique sees a communication language as an additional game rule. It can be used on top of any existing GGP-II player. This feature makes it a general algorithm. The main limitation of GL is its inability to solve large problems. Finally, I present the General Language Tree Search algorithm (GLTS). This algorithm extends the GL technique to be applicable to large games. It prioritises the communication languages according to their closeness to the most successful one. To validate my claim, I perform an experiment using GLTS by providing it with a Multi-Agent Path Finding with Destination Uncertainty problem. The GLTS algorithm successfully discovers the desired strategies by utilising the implicit communication among agents.

Human-Robot Interaction (HRI) research is examining ways to make human-robot (HR) communication more natural. Incorporating natural communication techniques is expected to make HR communication seamless and more natural for humans. Humans naturally incorporate implicit levels of communication, and including implicit communication in HR communication should provide tremendous benefit. The aim for this work was to evaluate a model for humanrobot implicit communication. Specifically, the primary goal for this research was to determine whether humans can assign meanings to implicit cues received from autonomous robots as they do for identical implicit cues received from humans. An experiment was designed to allow participants to assign meanings to identical, implicit cues (pursuing, retreating, investigating, hiding, patrolling) received from humans and robots. Participants were tasked to view random video clips of both entity types, label the implicit cue, and assign a level of confidence in their chosen answer. Physiological data was tracked during the experiment using an electroencephalogram and eye-tracker. Participants answered workload and stress measure questionnaires following each scenario. Results revealed that participants were significantly more accurate with human cues (84%) than with robot cues (82%), however participants were highly accurate, above 80%, for both entity types. Despite the high accuracy for both types, participants remained significantly more confident in answers for humans (6.1) than for robots (5.9) on a confidence scale of 1 - 7. Subjective measures showed no significant differences for stress or mental workload across entities. Physiological measures were not significant for the engagement index across v entity, but robots resulted in significantly higher levels of cognitive workload for participants via the index of cognitive activity. The results of this study revealed that participants are more confident interpreting human implicit cues than identical cues received from a robot. However, the accuracy of interpreting both entities remained high. Participants showed no significant difference in interpreting different cues across entity as well. Therefore, much of the ability of interpreting an implicit cue resides in the actual cue rather than the entity. Proper training should boost confidence as humans begin to work alongside autonomous robots as teammates, and it is possible to train humans to recognize cues based on the movement, regardless of the entity demonstrating the movement.

Shannon theory tells us how to communicate explicit sources across explicit channels. However, systems in nature and human society are rife with examples where neither the source nor channel is explicit, and actions, not words, appear to “speak.” This phenomena of what we can call implicit communication is little understood in the theory of control, and little explored in theory of communication. Consequently, almost no engineering systems systematically exploit implicit communication. In this dissertation, using toy models, we first argue that dramatic improvements could be possible in control precision and control costs with proper use of actions that communicate. Theoretically, implicit communication has proven to be a hard nut to crack. From a control stand-point, implicit communication makes problems hard because the same actions that are traditionally used exclusively for control can now communicate as well. From a communications view, there is often another conceptual difficulty: since the source is not specified explicitly, the message can be altered by control actions! Consequently, even the minimalist toy problem that distills these two difficulties --- the infamous Witsenhausen counterexample --- has remained unsolved for the past four decades. Worse, it is known to be NP-complete, ruling out the possibility of an algorithmic solution. Since the problem is hard as well as minimalist, it is a bottleneck in understanding implicit communication in particular and decentralized control in general. The main contribution of this dissertation is two-fold. First, using a sequence of three simplifications of the counterexample, we release this bottleneck by providing the first provably approximately-optimal solutions to the Witsenhausen counterexample. Second, we generalize this sequence of simplifications and propose them as a program for addressing more complicated problems of decentralized control. As an indication of the potential success of this program, we provide approximately-optimal solutions to various problems where implicit communication is possible. Using our refined understanding of implicit communication, we also identify a few practical situations where the phenomena may prove useful.