Effective coordination of agents' actions in partially-observable domains is a major challenge of multi-agent systems research. To address this, many researchers have developed techniques that allow the agents to make decisions based on estimates of the states and actions of other agents that are typically learnt using some form of machine learning algorithm. Nevertheless, many of these approaches fail to provide an actual means by which the necessary information is made available so that the estimates can be learnt. To this end, we argue that cooperative communication of state information between agents is one such mechanism. However, in a dynamically changing environment, the accuracy and timeliness of this communicated information determine the fidelity of the learned estimates and the usefulness of the actions taken based on these. Given this, we propose a novel information-sharing protocol, post-task-completion sharing, for the distribution of state information. We then show, through a formal analysis, the improvement in the quality of estimates produced using our strategy over the widely used protocol of sharing information between nearest neighbours. Moreover, communication heuristics designed around our information-sharing principle are subjected to empirical evaluation along with other benchmark strategies (including Littman's Q-routing and Stone's TPOT-RL) in a simulated call-routing application. These studies, conducted across a range of environmental settings, show that, compared to the different benchmarks used, our strategy generates an improvement of up to 60% in the call connection rate; of more than 1000% in the ability to connect long-distance calls; and incurs as low as 0.25 of the message overhead.

In recent years, we have witnessed the success of autonomous agents applying machine-learning techniques across a wide range of applications. However, agents applying the same machine-learning techniques in online applications have not been so successful. Even agent-based hybrid recommender systems that combine information filtering techniques with collaborative filtering techniques have been applied with considerable success only to simple consumer goods such as movies, books, clothing, and food. Yet complex, adaptive autonomous agent systems that can handle complex goods such as real estate, vacation plans, insurance, mutual funds, and mortgages have emerged.

In recent years, we have witnessed the success of autonomous agents applying machine-learning techniques across a wide range of applications. However, agents applying the same machine-learning techniques in online applications have not been so successful. Even agent-based hybrid recommender systems that combine information filtering techniques with collaborative filtering techniques have been applied with considerable success only to simple consumer goods such as movies, books, clothing, and food. Yet complex, adaptive autonomous agent systems that can handle complex goods such as real estate, vacation plans, insurance, mutual funds, and mortgages have emerged. To a large extent, the reinforcement learning methods developed to aid agents in learning have been more successfully deployed in offline applications. The inherent limitations in these methods have rendered them somewhat ineffective in online applications. In this article, we postulate that a small amount of prior knowledge and human-provided input can dramatically speed up online learning. We demonstrate that our agent HumanE -- with its prior knowledge or "experiences" about the real estate domain -- can effectively assist users in identifying requirements, especially unstated ones, quickly and unobtrusively.

Six high-level requirements drive the implementation of intelligent synthetic adversaries for training: (1) competence, (2) taskability, (3) observational fidelity, (4) behavior variability, most difficult tasks soldiers perform. Frequent Competence: The adversaries must perform training is an essential element in reducing the tactics and missions humans perform in casualties. For this application, the adversaries' environments is costly and restricted to physical goal is to defend a small multistoried mockups of buildings and small towns. The agents must move Environments (VIRTE) program is developing immersive virtual trainers for military operations through the environment, identify tactically on urbanized terrain (MOUT). In this relevant features (such as escape routes), and trainer, four-person fire teams of U.S. Marines communicate and coordinate with other are situated in a virtual urban environment and agents. Virtual opponents new missions for different training scenarios, are required to populate the environment and and they must change their objectives challenge the trainees. Behavior is not scripted or This article describes the general requirements specific to a particular mission, terrain, or operational for virtual MOUT opponents and our development setting, providing flexibility for operational of synthetic adversaries to meet use.

This paper extends the framework of partially observable Markov decision processes (POMDPs) to multi-agent settings by incorporating the notion of agent models into the state space. Agents maintain beliefs over physical states of the environment and over models of other agents, and they use Bayesian updates to maintain their beliefs over time. The solutions map belief states to actions. Models of other agents may include their belief states and are related to agent types considered in games of incomplete information. We express the agents' autonomy by postulating that their models are not directly manipulable or observable by other agents. We show that important properties of POMDPs, such as convergence of value iteration, the rate of convergence, and piece-wise linearity and convexity of the value functions carry over to our framework. Our approach complements a more traditional approach to interactive settings which uses Nash equilibria as a solution paradigm. We seek to avoid some of the drawbacks of equilibria which may be non-unique and do not capture off-equilibrium behaviors. We do so at the cost of having to represent, process and continuously revise models of other agents. Since the agent's beliefs may be arbitrarily nested, the optimal solutions to decision making problems are only asymptotically computable. However, approximate belief updates and approximately optimal plans are computable. We illustrate our framework using a simple application domain, and we show examples of belief updates and value functions.

(EDOC 2005). Moscow State University, Russia, King's Email: patrick.hung@uoit.ca In cooperation with the American Association for Artificial Intelligence General Chairs The 19th International FLAIRS Conference (FLAIRS 2006) will be held May 11-13 Philip Chan, Debasis Mitra 2006, in Melbourne Beach, Florida, USA. Coast" (centered around NASA's Kennedy Space Center), and has easy access to Florida Institute of Technology Orlando and the Disney World attractions. Submission of papers for presentation at the conference is now invited.

After rigorous evaluation, 150 papers were accepted for oral presentation, and 79 for poster presentation. The analogical and case based reasoning category features 6 papers; auctions and market-based systems features 5 papers, and automated reasoning ... out over the Ocean, the winter State University), Amy Greenwald features 12 papers. Twenty papers sky is brilliant panoply of (Brown University), Marti Hearst will be published in constraint stars and comets, beckoning to (University of California, Berkeley), satisfaction and satisfiability; game adventurers... who seek to divine Sridhar Mahadevan (University of theory and economic models features its mysteries. Machine his year marks the twenty-fifth for Artificial Intelligence pioneer and visionary Jay M. ("Marty") learning, the category with the and the twentieth National Tenenbaum4 who will speak on largest number of papers, has 35, Conference on AI (AAAI-05).1 The "The Future of AI and the Web"; while machine perception has 6.

Techniques in this symposium series were he calls the "twenty-first century for analyzing terrorist networks (1) AI Technologies for Homeland Security; strategic threat triad," which consists were reported by Alphatech (2) Challenges to Decision of failed states, global terrorism, and and the University of Arizona. Popp noted that and retrieving information for Robots: Verbal Interaction with convergence of these three elements counter intelligence was demonstrated Embodied Agents and Situated Devices; is highly destabilizing and a key by Jim Hendler of the University (5) Knowledge Collection from strategic concern to the national security of Maryland. They also aimed to chart out future from Stanford University, Lawrence For example, systems that are research agenda by identifying specific Livermore Laboratories, SRI International, based on probabilistic or decisiontheoretic interesting issues in various and Syracuse University. Homeland security applications for unable to cope with change by themselves, The recurrent themes from data mining and mobile robots were as neither probability theory the presentations included the following: reported by Alphatech and the University nor decision theory says much about of South Florida, respectively. How do The highlights of the symposium let alone how they should be modified.

Software agents can be used to automate many of the tedious, time-consuming information processing tasks that humans currently have to complete manually. However, to do so, agent plans must be capable of representing the myriad of actions and control flows required to perform those tasks. In addition, since these tasks can require integrating multiple sources of remote information ? typically, a slow, I/O-bound process ? it is desirable to make execution as efficient as possible. To address both of these needs, we present a flexible software agent plan language and a highly parallel execution system that enable the efficient execution of expressive agent plans. The plan language allows complex tasks to be more easily expressed by providing a variety of operators for flexibly processing the data as well as supporting subplans (for modularity) and recursion (for indeterminate looping). The executor is based on a streaming dataflow model of execution to maximize the amount of operator and data parallelism possible at runtime. We have implemented both the language and executor in a system called THESEUS. Our results from testing THESEUS show that streaming dataflow execution can yield significant speedups over both traditional serial (von Neumann) as well as non-streaming dataflow-style execution that existing software and robot agent execution systems currently support. In addition, we show how plans written in the language we present can represent certain types of subtasks that cannot be accomplished using the languages supported by network query engines. Finally, we demonstrate that the increased expressivity of our plan language does not hamper performance; specifically, we show how data can be integrated from multiple remote sources just as efficiently using our architecture as is possible with a state-of-the-art streaming-dataflow network query engine.

Many current large-scale multiagent team implementations can be characterized as following the ``belief-desire-intention'' (BDI) paradigm, with explicit representation of team plans. Despite their promise, current BDI team approaches lack tools for quantitative performance analysis under uncertainty. Distributed partially observable Markov decision problems (POMDPs) are well suited for such analysis, but the complexity of finding optimal policies in such models is highly intractable. The key contribution of this article is a hybrid BDI-POMDP approach, where BDI team plans are exploited to improve POMDP tractability and POMDP analysis improves BDI team plan performance. Concretely, we focus on role allocation, a fundamental problem in BDI teams: which agents to allocate to the different roles in the team. The article provides three key contributions. First, we describe a role allocation technique that takes into account future uncertainties in the domain; prior work in multiagent role allocation has failed to address such uncertainties. To that end, we introduce RMTDP (Role-based Markov Team Decision Problem), a new distributed POMDP model for analysis of role allocations. Our technique gains in tractability by significantly curtailing RMTDP policy search; in particular, BDI team plans provide incomplete RMTDP policies, and the RMTDP policy search fills the gaps in such incomplete policies by searching for the best role allocation. Our second key contribution is a novel decomposition technique to further improve RMTDP policy search efficiency. Even though limited to searching role allocations, there are still combinatorially many role allocations, and evaluating each in RMTDP to identify the best is extremely difficult. Our decomposition technique exploits the structure in the BDI team plans to significantly prune the search space of role allocations. Our third key contribution is a significantly faster policy evaluation algorithm suited for our BDI-POMDP hybrid approach. Finally, we also present experimental results from two domains: mission rehearsal simulation and RoboCupRescue disaster rescue simulation.