Planning is essential for an action-oriented, goal-driven software agent. In order to achieve a specific goal, an agent must first generate a plan. However, as the poet Robert Burns once noted, the best laid plans can often go awry. Each step of the plan is subject to the possibility of failure, a truth particularly relevant in the realworld or a realistic simulated environment. External influences not originally considered can often cause sudden, unanticipated consequences during the execution of the plan. When this happens, an intelligent software agent needs to answer the following important questions: What are the consequences of this event on its plan? How will the plan be affected? Can the plan be adjusted to accommodate the unanticipated effects? The research described in this thesis develops a model whereby intelligent agents can automatically determine consequences of unplanned events. Such a model provides agents with the ability to detect if and how events will affect the plan. This allows agents to subsequently modify the plan to mitigate unfavorable consequences or take advantage of favorable consequences.

In most video games today that focus on a single story, scripting languages are used for controlling the artificial intelligence of the virtual actors. While scripting is a great tool for reliably performing a story, it has many disadvantages; mainly, it is limited by only being able to respond to those situations that were explicitly declared, causing unreliable responses to unknown situations, and the believability of the virtual actor is hindered by possible conflicts between scripted actions and appropriate responses as perceived by the viewer. This paper presents a novel method of storytelling by manipulating the environment, whether physically or the agent's perception of it, around the goals and behaviors of the virtual actor in order to advance the story rather than controlling the virtual actor explicitly. The virtual actor in this method is completely autonomous and the environment is manipulated by a story manager so that the virtual actor chooses to satisfy its goals in accordance with the direction of the story. Comparisons are made between scripting, traditional autonomy, Lionhead Studio's Black & White, Mateas and Stern's Façade, and autonomy with environmental manipulation in terms of design, performance, believability, and reusability. It was concluded that molding an environment around a virtual actor with the help of a story manager gives the actor the ability to reliably perform both event-based stories while preserving the believability and reusability of the actor and environment. While autonomous actors have traditionally been used solely for emergent storytelling, this new storytelling method enables them to be used reliably and efficiently to tell event-based stories as well while reaping the benefits of their autonomous nature. In addition, the separation of the virtual actors from the environment and story manager in terms of design promotes a cleaner, reusable architecture that also allows for independent development and improvement. By modeling artificial intelligence design after Herbert Simon's “artifact,” emphasizing the encapsulation of the inner mechanisms of virtual actors, the next era of digital storytelling can be driven by the design and development of reusable storytelling components and the interaction between the virtual actor and its environment.

A Bayesian network approach to self-organization and learning is introduced for use with intelligent agents. Bayesian networks, with the help of influence diagrams, are employed to create a decision-theoretic intelligent agent. Influence diagrams combine both Bayesian networks and utility theory. In this research, an intelligent agent is modeled by its belief, preference, and capabilities attributes. Each agent is assumed to have its own belief about its environment. The belief aspect of the intelligent agent is accomplished by a Bayesian network. The goal of an intelligent agent is said to be the preference of the agent and is represented with a utility function in the decision theoretic intelligent agent. Capabilities are represented with a set of possible actions of the decision-theoretic intelligent agent. Influence diagrams have utility nodes and decision nodes to handle the preference and capabilities of the decision-theoretic intelligent agent, respectively. Learning is accomplished by Bayesian networks in the decision-theoretic intelligent agent. Bayesian network learning methods are discussed intensively in this paper. Because intelligent agents will explore and learn the environment, the learning algorithm should be implemented online. None of the existent Bayesian network learning algorithms has online learning. Thus, an online Bayesian network learning method is proposed to allow the intelligent agent learn during its exploration. Self-organization of the intelligent agents is accomplished because each agent models other agents by observing their behavior. Agents have belief, not only about environment, but also about other agents. Therefore, an agent takes its decisions according to the model of the environment and the model of the other agents. Even though each agent acts independently, they take the other agents behaviors into account to make a decision. This permits the agents to organize themselves for a common task. To test the proposed intelligent agent's learning and self-organizing abilities, Windows application software is written to simulate multi-agent systems. The software, IntelliAgent, lets the user design decision-theoretic intelligent agents both manually and automatically. The software can also be used for knowledge discovery by employing Bayesian network learning a database. Additionally, we have explored a well-known herding problem to obtain sound results for our intelligent agent design. In the problem, a dog tries to herd a sheep to a certain location, i.e. a pen. The sheep tries to avoid the dog by retreating from the dog. The herding problem is simulated using the IntelliAgent software. Simulations provided good results in terms of the dog's learning ability and its ability to organize its actions according to the sheep's (other agent) behavior. In summary, a decision-theoretic approach is applied to the self-organization and learning problems in intelligent agents. Software was written to simulate the learning and self-organization abilities of the proposed agent design. A user manual for the software and the simulation results are presented. This research is supported by the Office of Naval Research with the grant number N00014-98-1-0779. Their financial support is greatly appreciated. / Ph. D.

One of the major planning problems faced by medium and large manufacturing enterprises is the distribution of production over various (production) facilities. The need for cross-facility capacity management is most evident in the high-tech industries having capital-intensive equipment and short technology life cycle. There have been solutions proposed in the literature that are based on the lagragian decomposition method which separate the overall multiple product problem into a number of single product problems. We believe that multi-agent systems, given their distributed problem solving approach can be used to solve this problem, in its entirety, more effectively. According to other researchers who have worked in this field, auction theoretic mechanisms are a good way to solve complex production planning problems. This research study develops a multi-agent system and negotiation protocol based on combinatorial auction framework to solve the given multi-facility planning problem. The output of this research is a software library, which can be used as a multi-agent system model of the multi-product, multi-facility capacity allocation problem. The negotiation protocol for the agents is based on an iterative combinatorial auction framework which can be used for making allocation decisions in this environment in real-time. A simulator based on this library is created to validate the multi-agent model as well as the auction theoretic framework for different scenarios in the problem domain. The planning software library is created using open source standards so that it can be seamlessly integrated with scheduling library being developed as a part of the Advanced Planning and Scheduling (APS) system project or any other software suite which might require this functionality. The research contribution of this study is in terms of a new multi-agent architecture for an Advanced Planning and Control (APS) system as well as a novel iterative combinatorial auction mechanism which can be used as an agent negotiation protocol within this architecture. The theoretical concepts introduced by this research are implemented in the MultiPlanner production planning tool which can be used for generating master production plans for manufacturing enterprises. The validation process carried out on both the iterative combinatorial framework and the agent-based production planning methodology demonstrate that the proposed solution strategies can be used for integrated decision making in the multi-product, multi-facility production planning domain. Also, the software tool developed as part of this research is a robust, platform independent tool which can be used by manufacturing enterprises to make relevant production planning decisions. / Master of Science

Optimizing connected automated vehicle movements through roadway intersections is a challenging problem. Traditional traffic control strategies, such as traffic signals are not optimal, especially for heavy traffic. Alternatively, centralized automated vehicle control strategies are costly and not scalable given that the ability of a central controller to track and schedule the movement of hundreds of vehicles in real-time is highly questionable. In this research, a series of fully distributed heuristic algorithms are proposed where vehicles in the vicinity of an intersection continuously cooperate with each other to develop a schedule that allows them to safely proceed through the intersection while incurring minimum delays. An algorithm is proposed for the case of an isolated intersection then a number of algorithms are proposed for a network of intersections where neighboring intersections communicate directly or indirectly to help the distributed control at each intersection makes a better estimation of traffic in the whole network. An algorithm based on the Godunov scheme outperformed optimized signalized control. The simulated experiments show significant reductions in the average delay. The base algorithm is successfully added to the INTEGRATION micro-simulation model and the results demonstrate improvements in delay, fuel consumption, and emissions when compared to roundabout, signalized, and stop sign controlled intersections. The study also shows the capability of the proposed technique to favor emergency vehicles, producing significant increases in mobility with minimum delays to the other vehicles in the network. / Ph. D.

In this thesis we study a reasoning module for agents that have cognitive abilities, such as memory, perception, action, and are expected to function autonomously for long periods of time. The module provides the ability to reason about action and change using the language of the situation calculus and variants of the basic action theories. The main focus of this thesis is on the logical problem of progressing an action theory. First, we investigate the conjecture by Lin and Reiter that a practical first-order definition of progression is not appropriate for the general case. We show that Lin and Reiter were indeed correct in their intuitions by providing a proof for the conjecture, thus resolving the open question about the first-order definability of progression and justifying the need for a second-order definition. Then we proceed to identify three cases where it is possible to obtain a first-order progression with the desired properties: i) we extend earlier work by Lin and Reiter and present a case where we restrict our attention to a practical class of queries that may only quantify over situations in a limited way; ii) we revisit the local-effect assumption of Liu and Levesque that requires that the effects of an action are fixed by the arguments of the action and show that in this case a first-order progression is suitable; iii) we investigate a way that the local-effect assumption can be relaxed and show that when the initial knowledge base is a database of possible closures and the effects of the actions are range-restricted then a first-order progression is also suitable under a just-in-time assumption. Finally, we examine a special case of the action theories with range-restricted effects and present an algorithm for computing a finite progression. We prove the correctness and the complexity of the algorithm, and show its application in a simple example that is inspired by video games.

Dentre as várias áreas de pesquisa em Inteligência Artificial Distribuída, priorizamos analisar a comunicação entre os agentes de uma sociedade. É através da comunicação que os agentes podem trocar informações entre si e assim resolver de forma cooperativa um problema global ou local que existe na sociedade. A análise do fluxo de comunicação entre agentes é portanto de grande interesse da comunidade científica que se dedica à IAD. Neste trabalho, através do estudo teórico (análise matemática) e simulações computacionais, comparamos o fluxo de comunicação entre os agentes de dois modelos de organizações dinâmicas: uma organização em que os agentes realizam uma busca informada de um parceiro (Coalisão Baseada em Dependências - CBD) e uma organização em que os agentes realizam uma busca não informada de um parceiro (Rede Contractual - RC). O Sistema CENINT, um sistema multiagente (SMA) baseado no modelo RC, foi desenvolvido a fim de realizar as simulações necessárias para os estudos deste trabalho. Por outro lado, sabemos que os sistemas multiagentes são utilizados para desenvolver modelos teóricos que permitem elucidar a estrutura de processos complexos e que a orientação a objetos facilita o desenvolvimento de sistemas complexos. Percebeu-se que a orientação a objetos poderia ser uma ferramenta adequada para desenvolver sistemas multiagentes. Assim neste trabalho, optou-se por desenvolver o sistema CENINT utilizando as técnicas de orientação a objetos, mais especificamente utilizar os diagramas da UML (Unified Modeling Language) para análise e projeto do sistema.

Dentre as várias áreas de pesquisa em Inteligência Artificial Distribuída, priorizamos analisar a comunicação entre os agentes de uma sociedade. É através da comunicação que os agentes podem trocar informações entre si e assim resolver de forma cooperativa um problema global ou local que existe na sociedade. A análise do fluxo de comunicação entre agentes é portanto de grande interesse da comunidade científica que se dedica à IAD. Neste trabalho, através do estudo teórico (análise matemática) e simulações computacionais, comparamos o fluxo de comunicação entre os agentes de dois modelos de organizações dinâmicas: uma organização em que os agentes realizam uma busca informada de um parceiro (Coalisão Baseada em Dependências - CBD) e uma organização em que os agentes realizam uma busca não informada de um parceiro (Rede Contractual - RC). O Sistema CENINT, um sistema multiagente (SMA) baseado no modelo RC, foi desenvolvido a fim de realizar as simulações necessárias para os estudos deste trabalho. Por outro lado, sabemos que os sistemas multiagentes são utilizados para desenvolver modelos teóricos que permitem elucidar a estrutura de processos complexos e que a orientação a objetos facilita o desenvolvimento de sistemas complexos. Percebeu-se que a orientação a objetos poderia ser uma ferramenta adequada para desenvolver sistemas multiagentes. Assim neste trabalho, optou-se por desenvolver o sistema CENINT utilizando as técnicas de orientação a objetos, mais especificamente utilizar os diagramas da UML (Unified Modeling Language) para análise e projeto do sistema.

There is an overwhelming variation in the ways an intelligent agent can rationalize communication with a conversational partner. This variation presents many incompatibilities that lead to the specialization of conversational capabilities. This has produced a plethora of models and ideas on how an intelligent agent should understand, interact with, and incorporate communication from a human conversational participant. This dissertation approaches this problem with the thesis that there exists a language between that of human natural language and the behavioral reasoning of an intelligent agent, and that this language is capable of not only unifying the various models used in literature, but also provides the foundation for a theoretical framework for an engineering methodology for building such models. A theory of practical communication language is developed, including the introduction of the meaning-action concept, an expressive and powerful representation based on speech-act and dialogue-act theories, but extended with notions of behavioral operators as well as signatures that allow the operators to incorporate structured and well-defined concepts. An engineering methodology is presented for the construction of concepts, operators and rules that create the language and model of a specific domain, including methodology for the verification and validation of that language and model. The resultant practical communication language methodology, based on the combination of rational communication and meaning-action concepts, will introduce several major enhancements to dialogue management. These enhancements include the use of meaning-action concepts as a shared medium and the introduction of a shared concept graph. This methodology will be used along with various dialogue models from human-human, human-agent and agent-agent communication to construct a task-oriented language and model called the task communication language framework. This framework is then implemented within an intelligent agent in a real-time resource management simulation. A sample output listing from actual human interaction with that implementation is used to demonstrate that the resulting framework does indeed incorporate many of the disparate models of communication and their corresponding capabilities including command and control, information seeking, notification and bother, clarification, explanation, discussion, negotiation, mutual planning, interruption, feedback, adjustable autonomy and corrective dialogues.

In this thesis we study a reasoning module for agents that have cognitive abilities, such as memory, perception, action, and are expected to function autonomously for long periods of time. The module provides the ability to reason about action and change using the language of the situation calculus and variants of the basic action theories. The main focus of this thesis is on the logical problem of progressing an action theory. First, we investigate the conjecture by Lin and Reiter that a practical first-order definition of progression is not appropriate for the general case. We show that Lin and Reiter were indeed correct in their intuitions by providing a proof for the conjecture, thus resolving the open question about the first-order definability of progression and justifying the need for a second-order definition. Then we proceed to identify three cases where it is possible to obtain a first-order progression with the desired properties: i) we extend earlier work by Lin and Reiter and present a case where we restrict our attention to a practical class of queries that may only quantify over situations in a limited way; ii) we revisit the local-effect assumption of Liu and Levesque that requires that the effects of an action are fixed by the arguments of the action and show that in this case a first-order progression is suitable; iii) we investigate a way that the local-effect assumption can be relaxed and show that when the initial knowledge base is a database of possible closures and the effects of the actions are range-restricted then a first-order progression is also suitable under a just-in-time assumption. Finally, we examine a special case of the action theories with range-restricted effects and present an algorithm for computing a finite progression. We prove the correctness and the complexity of the algorithm, and show its application in a simple example that is inspired by video games.