CORAL Seminar

Several tasks, such as plan reuse and agent modelling, need to interpret a given or observed plan to generate the underlying plan rationale. Although there are several previous methods that successfully extract plan rationales, they do not apply to complex plans, in particular to plans with actions that have conditional effects. I will discuss the SPRAWL algorithm for finding a minimal annotated partially ordered structure in an observed totally ordered plan with conditional effects. The algorithm proceeds in a two-phased approach, first preprocessing the given plan using a novel needs analysis technique that builds a needs tree to identify the dependencies between operators in the totally ordered plan. The needs tree is then processed to construct a partial ordering that captures the complete rationale of the given plan. I will provide illustrative examples and discuss the challenges we faced.

I'll be giving an overview of my recent (and ongoing) literature survey on MDP-style models and algorithms. I'll be discussing the major variations, restrictions, and refinements in the models and some interesting algorithms from the literature. I'll be focusing on single and no agent models and algorithms, mostly because the multi-agent variations are a very large can of worms. Come prepared to critique me in your area of specialty, point out important work which I have missed, and ask me lots of questions (which I hope I'll be able to answer). In order to maintain order in the room, the word "coach" will not be used in the talk.

There is a very rich variety of systems of autonomous agents, be it software or robotic agents. In particular, multi-agent systems can include agents that may be part of a team and need to coordinate their actions during their distributed task execution. This coordination requires an agent to observe, i.e., to monitor, the other agents in order to detect a possible coordination failure of the team. Several researchers have addressed the problem of monitoring for single or multiple agent systems and have contributed successful, but mainly application-specific, approaches. In this paper, we aim at contributing a unifying, domain-independent statement of the distributed multi-agent monitoring problem. We define the problem in terms of a pre-defined _desirable joint state_ and an _observation-state mapping_. Given a concrete joint observation during execution, we show how an agent can detect a possible coordination failure by processing the observation-state mapping and the desirable joint state. To illustrate the generality of our formalism, one of the main contributions of the paper, we represent several previously studied examples within our formalism. We note that basic failure detection algorithms can be computationally expensive. We further contribute an efficient method for failure detection that builds upon an off-line compilation of the principled relations introduced. We show empirical results that demonstrate this effectiveness.

The recent surge in research on multiagent learning has focused on marrying the ideas of reinforcement learning and game theory. This marriage has adopted the game theoretic concept of Nash equilibria as one of its foundations. Equilibria rely critically on the assumption that all agents are rational and play optimally. Reinforcement learning on the other hand has been tackling the scaling problem by sacrificing this very thing, optimality, in favor of less memory and time. This talk will explore the question of what happens to equilibria when agents are no longer optimal. The first part of this talk will consist of a brief tutorial on game theory and multiagent learning. The second part will then focus on limitations that prevent agents from playing optimally, examining the affect these limitations have on agent behavior and ultimately on the existence of equilibria. Proofs and counterexamples will abound. Finally, tentative conclusions will be drawn from these results. Note that the title question will not be answered and is purely for shock value.