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.

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.

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.

Der Begriff ``Agent'' hat sich als eine sehr nützliche Abstraktion erwiesen, um verschiedene Problembereiche auf eine intuitive und natürliche Art und Weise zu konzeptualisieren. Intelligente Agenten haben daher Anwendung gefunden in verschiedenen Teilbereichen der Informatik. Zur Modellierung werden intelligente Agenten meist als intentionale Systeme aufgefaßt und mit Hilfe von mentalistischen Begriffen wie Wissen, Glauben (oder Überzeugung), Wunsch, Pflicht, Intention usw. beschrieben. Unter diesen mentalen Begriffen gehören die epistemischen Begriffe (d.h., Wissen und Glauben) zu den wichtigsten und wurden auch am intensivsten untersucht. Zur Modellierung von Wissen und Glauben werden in der Regel modale epistemische Logiken verwendet. Solche Systeme sind aber nicht geeignet, um ressourcenbeschränkte Agenten zu beschreiben, weil sie zu starke Annahmen bezüglich der Rationalität von Agenten machen. Zum Beispiel wird angenommen, daß Agenten alle logischen Wahrheiten sowie alle Konsequenzen seines Wissens kennen. Dieses Problem ist bekannt als das Problem der logischen Allwissenheit (``logical omniscience problem''). Da alle Agenten grundsätzlich nur über begrenzte Ressourcen (wie z.B. Zeit, Information, Speicherplatz) verfügen, können sie nur eine begrenzte Menge von Informationen verarbeiten. Daher müssen alternative Modelle entwickelt werden, um Agenten realistisch modellieren zu können (siehe Kapitel 2). Daß modale epistemische Logik für die Formalisierung des ressourcenbeschränkten Schließens (``resource-bounded reasoning'') nicht geeignet ist, wird als ein offenes Problem der Agententheorien anerkannt. Es gibt bisher aber keine brauchbaren Alternativen zur Modallogik. Die meisten Ansätze zur Lösung des logischen Allwissenheitsproblems versuchen, Wissen und Glauben mit Hilfe schwacher Modallogiken zu beschreiben. Solche Versuche sind nicht befriedigend, da sie eine willkürliche Einschränkung der Rationalität der Agenten zur Folge haben (siehe Kapitel 3). Mein Ziel ist es, einen Rahmen für das ressourcenbeschränktes Schließen über Wissen und Glauben zu entwickeln. Damit soll eine solide Grundlage für Theorien intelligenter Agenten geschaffen werden. Als Nebenergebnis wird das logische Allwissenheitsproblem auf eine sehr intuitive Art und Weise gelöst: obwohl Agenten rational sind und alle logischen Schlußregeln anwenden können, sind sie nicht logisch allwissend, weil ihnen nicht genügend Ressourcen zu Verfügung stehen, um alle logischen Konsequenzen ihres Wissens zu ziehen. Im Kapitel 4 wird eine Reihe von Logiken vorgestellt, die den Begriff des expliziten Wissens formalisieren. Es wird eine Lösung des Problems der logischen Allwissenheit der epistemischen Logik vorgeschlagen, die die Rationalität der Agenten nicht willkürlich einschränkt. Der Grundgedanke dabei ist der folgende. Ein Agent kennt die logischen Konsequenzen seines Wissens nur dann, wenn er sie tatsächlich hergeleitet hat. Wenn ein Agent alle Prämissen einer gültigen Schlußregel kennt, kennt er nicht notwendigerweise die Konklusion: er kennt sie nur nach der Anwendung der Regel. Wenn er den Schluß nicht ziehen kann, z.B. weil er nicht die notwendigen Ressourcen dazu hat, wird sein Wissen nicht um diese herleitbare Information erweitert. Die Herleitung neuer Informationen wird als die Ausführung mentaler Handlungen aufgefaßt. Mit Hilfe einer Variante der dynamischen Logik können diese Handlungen beschrieben werden. Im Kapitel 5 werden Systeme für das ressourcenbeschränkte Schließen über Wissen und Glauben entwickelt, die auch quantitative Bedingungen über die Verfügbarkeit von Ressourcen modellieren können. Mit Hilfe dieser Logiken können Situationen beschrieben werden, wo Agenten innerhalb einer bestimmten Zeitspanne entscheiden müssen, welche Handlungen sie ausführen sollen. Der Ansatz besteht darin, epistemische Logik mit Komplexitätstheorie zu verbinden. Mit Hilfe einer Komplexitätsanalyse kann ein Agent feststellen, ob ein bestimmtes Problem innerhalb vorgegebener Zeit lösbar ist. Auf der Grundlage dieses Wissens kann er dann die für die Situation geeignete Entscheidung treffen. Damit ist es gelungen, eine direkte Verbindung zwischen dem Wissen eines Agenten und der Verfügbarkeit seiner Ressourcen herzustellen. / One of the principal goals of agent theories is to describe realistic, implementable agents, that is, those which have actually been constructed or are at least in principle implementable. That goal cannot be reached if the inherent resource-boundedness of agents is not treated correctly. Since the modal approach to epistemic logic is not suited to formalize resource-bounded reasoning, the issue of resource-boundedness remains one of the main foundational problems of any agent theory that is developed on the basis of modal epistemic logic. My work is an attempt to provide theories of agency with a more adequate epistemic foundation. It aims at developing theories of mental concepts that make much more realistic assumptions about agents than other theories. The guiding principle of my theory is that the capacities attributed to agents must be empirically verifiable, that is, it must be possible to construct artificial agents which satisfy the specifications determined by the theory. As a consequence, the unrealistic assumption that agents have unlimited reasoning capacities must be rejected. To achieve the goal of describing resource-bounded agents accurately, the cost of reasoning must be taken seriously. In the thesis I have developed a framework for modeling the relationship between knowledge, reasoning, and the availability of resources. I have argued that the correct form of an axiom for epistemic logic should be: if an agent knows all premises of a valid inference rule and if he performs the right reasoning, then he will know the conclusion as well. Because reasoning requires resources, it cannot be safely assumed that the agent can compute his knowledge if he does not have enough resources to perform the required reasoning. I have demonstrated that on the basis of that idea, the problems of traditional approaches can be avoided and rich epistemic logics can be developed which can account adequately for our intuitions about knowledge.

Thesis (M.App.Sc.) - Carleton University, 2005. / Includes bibliographical references (p. 172-178). Also available in electronic format on the Internet.

Logic-based formalizations of dynamical systems are central to the field of knowledge representation and reasoning. These formalizations can be used to model agents that act, reason,and perceive in a changing and incompletely known environment. A key aspect of reasoning about agents and their behaviors is the notion of joint ability. A team of agents is jointly able to achieve a goal if despite any incomplete knowledge or even false beliefs about the world or each other, they still know enough to be able to get to a goal state, should they choose to do so. A particularly challenging issue associated with joint ability is how team members can coordinate their actions. Existing approaches often require the agents to communicate to agree on a joint plan. In this thesis, we propose an account of joint ability that supports coordination among agents without requiring communication, and that allows for agents to have incomplete (or even false) beliefs about the world or the beliefs of other agents. We use ideas from game theory to address coordination among agents. We introduce the notion of a strategy for each agent which is basically a plan that the agent knows how to follow. Each agent compares her strategies and iteratively discards those that she believes are not good considering the strategies that the other agents have kept. Our account is developed in the situation calculus, a logical language suitable for representing and reasoning about action and change that is extended to support reasoning about multiple agents. Through several examples involving public, private, and sensing actions, we demonstrate how symbolic proof techniques allow us to reason about team ability despite incomplete specifications about the beliefs of agents.