![[LOGO IME ARQUIMEDES]](ime-arquimedes.png) |
University
of São Paulo Institute of Mathematics and Statistics Department of Computer Science LIDET - Laboratory of Interactivity and Digital Entertainment Technology |
![[USP LOGO]](usp-brasao.png) |
This document describes my undergraduate research project at the university. The text has two parts. The first one describes the technical aspects of the project. The second one describes its relationship with the Computer Science course.
An intelligent agent acts based on its perceptions and on its knowledge base. However, the knowledge base itself can be the subject of actions, for example when it is updated because its contents conflict with the perceptions. This happens when a perception enters in conflict with the predicates at the knowledge base. Truth maintenance systems (TMS) are mechanisms that aim to make it possible for an intelligent agent to revise and update its knowledge base.
Within the project, a simplified version of a TMS has been devised and an implementation of this theory has been done.
In the following sections, the technical aspects of the project are described. It is assumed that the reader understands some basic concepts of Computer Science. It is not assumed, however, that the reader knows what is studied in the Artificial Intelligence field.
In the following subsections, the motivations, objectives and problems of this project are described. Also, a tiny introduction to the Artificial Intelligence field is presented, together with the contextualization of this project.
It has been long advocated in academia and industry that artificial intelligence can greatly improve the “believability” of characters in computer games, especially those characters not controlled by human players [1]. In many cases, however, the AI techniques employed in the design of agents for computer games is quite simplistic if compared to the most sophisticated techniques produced by the AI research community.
Taking into account that computer games usually attract extremely skillful programmers who know exactly what the goals of their projects are, we would not consider surprising that the inclusion of more convoluted AI techniques had little impact in the final behaviour of programmed agents. However, these more sophisticated techniques can greatly improve the process of design and implementation of intelligent agents for computer games, chiefly due to the possibility of allowing agent designers and programmers to focus on the appropriate level of abstraction.
The main goal of this project was to implement a TMS in a bot of the game Guntactyx and to verify whether this bot could win more battles than bots without a TMS. To accomplish this, a simplification of the original assumption-based truth maintenance system (ATMS) had to be developed. This simplification has been named Simplified Assumption-based Truth Maintenance System (SATMS).
The SATMS suggests a very natural sensing-deliberate-act architecture to program agents capable of revising their knowledge base.
Our first goal was to prove that sophisticated reasoning architectures such as the SATMS could be employed to program agents even for action games with no losses in computational performance. Our second goal was to demonstrate that one such reasoning architecture could release designers and programmers from having to deal with low level agent programming, thus making the design and revision of these agents more flexible and agile.
The original paper by de Kleer [2] proved to be a very difficult reading. His paper describes the ATMS, which is the base theory behind the SATMS. To understand and extract the essence of his idea came to be very challenging.
The next step was to implement the SATMS and its sensing-deliberate-act architecture into some game and extract some results. The Guntactyx programming game proved to be a good alternative to prototype an AI script to test the SATMS and its architecture. The problem with choosing Guntactyx as the prototyping platform was its scripting language. The language used by the game is the SMALL language. It is a very simple language with a C-like syntax. Within this language, the more complex data-strutucte available is the two-dimensional array. Implementing the SATMS using only arrays came to be another challenge.
Artificial Intelligence (AI) can be seen as the study of agents that observe the environment and perform actions. Each such agent may be viewed as implementing a function that maps sequences of observations into actions. AI attempts not just to understand but also to build intelligent entities. It systematizes and automates intellectual tasks and is therefore potentially relevant to any sphere of human intellectual activity [3].
AI is being used successfully to do autonomous planning and scheduling (NASA's Remote Agent), game playing (IBM's Deep Blue), autonomous control (ALVINN computer vision system), diagnosis (MYCIN), logistics planning (DART), robotics (HipNav) and language understanding and problem solving (PROVERB).
Human beings are capable to revise their beliefs when they note that something is wrong. For example, a human knows that when he steps on in the brake of a car, the car will stop within some milliseconds. However, this belief can be retracted from his knowledge by himself if the car that he is driving is over an icy road. Together with retracting this wrong belief that the car should stop within milliseconds, he will probably add a new belief that tells him that the car will break not within milliseconds anymore, but within seconds.
Humans revise their beliefs very often. Shouldn't us try to replicate this ability into a computer agent? Wouldn't the agent appear more real with this ability? This ability is exactly what we have developed and implemented, in some smaller scale, into a bot of the game Guntactyx.
In the following subsections, some key concepts and technologies used and developed within the project are explained in greater detail. First, the intelligent agent concept is presented. Next, the role of bots and non-player characters (NPCs) in computer games is explained in some detail. Following this explanation, truth maintenance systems in general, assumption-based truth maintenance system in particular and the developed simplified assumption-based truth maintenance system are explained. At last, a brief introduction to the workings of the Guntactyx programming game is shown together with the justifications of Guntactyx being the platform of choice for testing the theory developed.
The main unifying theme of the Artificial Intelligence field is the idea of an intelligent agent [3]. An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. A simple concept can help us to understand if an agent is working "well". This concept is the performance measure. The performance measure embodies the criterion for success of an agent's behavior.
A natural performance measure for bots using the SATMS is its winning count. As mentioned before, besides measuring the winning performance of a bot with SATMS, there was an interest to demonstrate that there is no computational performance loss using the SATMS and that its suggested architecture can make the life of the agent designer and programmer a lot easier.
The bots of Guntactyx can easily be seen as intelligent agents. They can sense the environment around them and they can act upon it. From now on, the terms bot and intelligent agent will be used interchangeably.
A bot is a roBOTic computer controlled entity that simulates human intellectual faculties. Computer game bots work via artificial intelligence routines pre-programmed to suit the game map, game rules, game type and other parameters unique to each game. Bots can help a PC gamer learn the gameplay environment and the game rules as well as help them practice shooting accuracy and gaming skills before going online to compete with other human players in a multiplayer environment.
In Guntactyx, however, the purpose of the game is exactly to write bots. More on Guntactyx later.
Non-player characters (NPCs) are characters in a game whose actions are determined by the game AI. Non-player characters populate the fictional world of the game - from the friendly innkeeper in Dungeons & Dragons to a taxi driver or a computer hacker in a contemporay or futuristic game. Non-player characters (NPCs) might be allies, bystanders or competitors to the player characters (PCs).
Truth maintenance systems (TMS) are mechanisms for keeping track of dependencies and detecting inconsistency [4]. Some authors prefer the term belief revision instead of truth maintenance system. From now on we will use the terms belief revision and truth maintenance system interchangeably.
There are several ways to perform belief revision. They are:
There are two main flavors of TMS. They are the Justification-based truth maintenance system (JTMS) and the Assumption-based truth maintenance system (ATMS). The former is based on non-monotonic justifications. The latter, on hypothetical reasoning.
The ATMS has been the base theory for the simplified assumption-based truth maintenance system (SATMS) developed in this research.
Sometimes it is convenient to perform reasoning in the context of different hypothetical worlds, which may or may not resemble the way the world actually is. This strategy is particularly useful if there are a large number of hypotheses competing to account for the observations, with the possibility that a composite hypothesis may be required to cover all of them.
In an assumption-based truth maintenance system (ATMS), the program maintains a number of different contexts, referred to as environments. An environment is best thought of as a view of the world characterized by a set of assumptions [4].
The environments of an ATMS can be arranged in a lattice, since the making of assumptions is an incremental thing. As we go up the lattice, hypothetical worlds become more and more specific, in the sense that we know more and more about them.
The context of an environment is the set of propositions derivable from the assumptions and the facts of the world model. Inconsitent contexts are called nogoods.
There are dependencies between the individual assumptions that we might make, and these dependencies must be recorded and enforced. These dependencies are part of the input to the program. The ATMS then constructs, for each propositional node, a label which lists the interesting environments that that proposition holds in.
The basic purpose of an ATMS is to construct a list of the interesting environments in which a proposition holds. Such a list is defined as a sound, complete, consistent and minimal label, where a label is:
If a propositional node has an empty label, this means that the proposition is not derivable from any consistent set of assumptions. In other words, it is not to be found in the context of any environment that is consistent with the justifications.
One can think of the ATMS as being a dynamic structure that maintains dependencies among assumptions. Given a proposition, it can construct a label for that propostion telling in which environments it holds. With this structure, it is straightforward to add and retract assumptions and still be capable to check wheter or not a proposition still holds, without having to make a lot of inferences.
This theory could do more things than we wanted to. We didn't want the agent to think with an arbitrarily large set of assumptions and propositions. It is also computationally complex, and thus hardly feasible for programming agents for action games that have to reason and act in real time about changes in the environment. Because of that, we devised a simplified version of this theory, which is explained in the next section.
This system is based on three basic concepts: assumption, observation and action [5].
An assumption is a general statement about the world, e.g.
“friendly troops under siege” or
“friendly troops are
at advantage”. For reasons that will
become clear in the following paragraphs, it is assumed that each agent
must manage a relatively small set of assumptions, typically less then
ten. The set of assumptions will be denoted as A.
An observation is what results from the sensors of the agent. The set of observations will be denoted as O. It will be assumed that there is a partial function F, that associates a set of observations to an assumption.
Finally, an action is what can be sent to the actuators of the agent to determine its behavior. The set of actions will be denoted as C. It will be assumed that there is a partial function G, that associates a set of actions to an assumption.
Considering the set of subsets of A and the subset relation, one can think of the natural lattice of subsets of A. It will be assumed that some subsets of A are deemed as inconsistent subsets of assumptions. By definition, it will be stated that if a set of assumptions U contains an inconsistent set of assumptions V, then it is also inconsistent.
These concepts suggests that each agent could behave based on a sensing-deliberation-action cycle. Sensing generates a set of observations O. This set of observations O is related to some assumptions A'. Now, A' is a subset of A. If all sensors of the agent were fully reliable and consistent with each other, then A' should necessarily be a consistent subset of assumptions. This is not the case, however, and hence A' may be inconsistent.
If A' is inconsistent, we generate the maximal consistent subsets of A', denoted as A1, ..., An. Deliberation in this model amounts to deciding which of these maximal consistent sets of assumptions is the currently valid one. In the implementation that has been done, we simply pick one set at random.
Finally, given that the set of assumptions Ai is assumed as the present one, action amounts to determining and executing the set of actions C given by the union of all G(A): {A belongs to Ai}.
The main difference between this theory just described and the original ATMS, is that this simplified version assumes that all assumptions are fixed. Besides, it assumes that the inconsistent sets of assumptions are known a priori. The SATMS's job is just to give us one maximal consistent set of assumptions from an inconsistent set.
The goal of the Guntactyx programming action game is to test scripts made by the players that encode the behavior of agents. While in most games one has to actually play it in real time, in Guntactyx you program your team's behaviour – usually employing AI techniques - and then just watch them interacting in the game's environments.
There are three modes of play, each of which with different objectives: Fight, Soccer and Race. In Fight mode, warriors hold a weapon so they can shoot bullets or grenades. Health, energy and the other warrior's properties change according to some rules. The game includes three levels that are tailored for fights. The main purpose of this mode is to kill all the enemy teams. In Soccer mode, the objective of every team of warriors is to send the ball in the goal area of enemy teams. In Race mode, the objective of the warriors is to move around the origin in the counter-clockwise direction avoiding the obstacles of the level.
In this project we focused in the fighting mode.
The scripts must be written in SMALL, which is a language that resembles C with a lot of simplifications. The game provides a function library that the scripts can import. This library includes all the necessary functions to interact with the environment. Once compiled, one has only to copy its compiled script into a specified subdirectory in the game's installation directory to be able to chose it once the game is running.
According to the Guntactyx's author, the SMALL language was chosen because of the ease of manipulation by the interpreter. The game engine executes exactly the same number of instructions from each game bot script, thus making the simulation very fair and reliable.
In general, the Guntactyx programming game offers a very good environment for prototyping AI-based game scripts. This is due to its fairness and its rich application program interface that the bot can use to interact with the world.
This research project has begun in May, 2005 together with the creation of the LIDET - Laboratory of Interactivity and Digital Entertainment Technology.
The group meets from fifteen to fifteen days. In this meetings we discuss our works and next steps. Also, we do some meetings only with a member and the supervisor, to discuss that member's particular project.
My project had the following landmarks:
This research produced a theoretical result and a concrete implementation. The theoretical result is the SATMS. We can think of the SATMS as being an algorithm and an architecture for building agents capable to revise their knowledge bases. It can be implemented in most languages and is quite efficient.
The concrete implementation is the satmsBot, which is a bot that works within the Guntactyx programming game. His knowledge base can easily be seen in the code, as the code is very well documented.
Also, a satmsBot2 has been built to show that with only one line of code, a bot can act very different. The difference between satmsBot and satmsBot2 is that the second one can see bullets closer and that he doesn't runs towards the enemies once he can see one.
We have also written an article based on the SATMS, that was presented at the IV Workshop Brasileiro de Jogos e Entretenimento Digital 2005 [5].
The SATMS can be employed to program agents even for action games with no losses in computational performance. The fact that the satmsBot can win battles proves this.
The SATMS separates the abstract knowledge engineering from the low-level sensors and actions programming. A whole team of programmers could be assigned to program the low-level aspects of an agent. Another team could work on the knowledge of the agent. This other team has no need to be made of programmers. It can even consist only of psychologists, so that the agent can really think and act like a human.
With some predefined actions, observations and assumptions, a visual tool for associating them could generate the code easly. This is due to the uniformity of the code when the SATMS architecture is applied.
SATMS does not ensure that a bot using it will win every battle. However, the difference between a winning bot and a loosing bot can be a single line of code. This line is the one that associates actions to assumptions.
In the following sections, the subjective aspects of the project are described. The objective of this part is to relate this research project with the Computer Science course at the university. The first section describes the obstacles and frustations encountered during the research. Next, the more important disciplines to the project are presented. The role of my supervisor and the differences of a research project and an undergraduate project are presented next. At last, how the university helped to learn to transform theory into practice and the next step in search of more knowledge in the field are described.
During this research, the greatest obstacle encountered was the SMALL language's lack of more advanced data structures. The only data structure avaiable in this language is the array. All the SATMS relations had to be implemented using arrays.
Another obstacle was the lack of texts about the TMS and ATMS. I had to gather all the information found in [3], [4] and [6] to really understand the underneath theory of the ATMS.
The small scale of the SATMS came to be a frustration in the beginning. But after implementing it, I saw that it had to be that way due to its increasing complexity with a larger number of assumptions. However, the separation of low-level and high-level knowledge engineering compensates the SATMS's small scale.
The supervisor is a person who has already produced new knowledge. Without his help, it is quite difficult to know where to start and which theories and technologies are the top in any field of knowledge.
It has been my supervisor who suggested the ATMS simplification. Without this simplification, it would be impossible to implement a TMS in a bot of Guntactyx. We had periodic meetings to discuss the project. Also, he reviewed all my writtings, including this monograph, posters and slides used to present this research.
Many professors at the university wanted to guide me into some research. This came to be very satisfying. I've been able to choose the field and the theme that I wanted to do research.
The main difference between research projects and undergraduate projects is that in the former we can work with cutting edge theories and technologies, while in the last we study classic theories and concepts. It is very important to study classic theories and concepts, but to develop a new theory and produce new technologies is quite satisfying. When we do research, we are making and discovering new knowledge for the human kind.
It would be impossible to me to do research without the great background that I had at the university. All that mathematics and statistics helped me to develop a highly formal way of thinking. The only way to implement something in a computer is to have it formalized in a very precise manner.
Almost all problems given to us during the undergraduation are already formalized. When we are researching, we must not only solve problems, but also discover the problems that we need to solve and formalize them, before being able to solve them.
The university had a very important role in making me capable to transform theory into practice. Due to the high number of practical problems and exercises that we have to solve and implement solutions, our ability to use the theory learned increased enormously.
There are several steps that could be taken from now on in search of more knowledge. The first thing would be to study how to implement computational learning in an efficient manner into a game. Next, it would be interesting to try to integrate the SATMS with this new learning module, making the bot capable to learn with the opponents, in the case of a bot of Guntactyx.
Another thing to do would be to try to increase the capacity of the SATMS to deal with more assumptions while maintaining its efficient performance. Also, it would be nice to give weights to the sensors, so that the SATMS could choose an environment that has greater probability of being the right one, instead of choosing one randomly.
I would like to thank my parents, Fauzi and Rachel. They provided me all the resources to be able to study in full time and had all the patience needed to support my never ending studying at the weekends and never being with them.
I would like to thank my girlfriend, Camila, who doesn't have much to do with computer programming but who has everything to do with enriching the rest of my life in more ways than I could possibly describe. And also, who has the most patience in the world with me and my hard studying.
I would like to thank my supervisor, Flavio, for all his insights and ideas and his great orientation in the search for innovations.
|
University
of São Paulo Institute of Mathematics and Statistics Department of Computer Science LIDET - Laboratory of Interactivity and Digital Entertainment Technology |
|