Abstract

Because of Java's cross platform capabilities and object orientation it offers a unique solution to the demands of agent driven systems. Boundaries between agent knowledge, scope of operation, and nature of operation can be modeled very elegantly in an object-oriented environment. By the availability of this and the vast inter-connectivity offered by the Internet it is reasonable to expect agent systems and the data they operate on to approach a more distributed topology.

This research presents two object-oriented solutions to modeling the physical world. Attention is given to abstracting the data set so that these principals can be applied to other problems. Resulting from this research is also the Sadwoja API for Java for use in modeling the physical world.

During the semester of Fall 2000, Dr. Wolz ran a course in Game AI. During the course of that semester Tic-Tac-Toe was examined as a toy problem and expanded into an exploration of various implementations of solutions to problems solved by AI. Rule, Mini-max, and agent solutions were all applied to the problem of Tic-Tac-Toe and comparisons made.

Coming out of the course there was a hanging interest in developing a system in which AI could be applied easily to an object and have it operate in a world shared with other objects also running some implementation of AI. The initial intention was for comparing agent implementations and tweaks made to values in an agent system. By this agents could be shown to exhibit a variety of game play personalities, including optimal play.

The resulting research lead to a more general exploration of creating a world in which AI could be easily applied to objects and changed. Distribution over a network was also important as it would allow people to very easily put all their AI solutions into a common situation, and see which one performed best, most intelligently, most aggressively, etc. Produced by this research is a careful look at two models for modeling a physical world using Java. Also the Java class suite, Sadwoja came out as an actual endeavor to implement the favored solution.

Before beginning on this research the goal was set to have the end model, which would be implemented in what is now Sadwoja, be capable of simulating interactions that might take place in the physical world. Setting the end model goal as the physical world forces the end model to contend with the source of most problems. Much of the problems encountered by agent systems and the associated AI is in dealing with real world situations. As such, being able represent a model of the real world with all relevant data, and have a piece of software navigate it goes a long way to proving the model's viability. More importantly, the physical world is an object-oriented environment.

Using the physical world as a model also forces confrontation with problems associated with localization of data and data domains. Both of these problems relate very closely to one another. When modeling the physical world, most of the data is accessible by all agents, but not all data will be accessed by all agents. Nor will this data be altered by all agents or even dealt with by any agents. What this describes is the data domain that an agent is in. The data domain of an agent is that data which the agent must contend with. This set can change as the agent performs its task. The data domain also can help determine data localization.

Is all the information shared with everyone? Is some information irrelevant? Who makes that decision, an agent, or many agents? Localization deals with data filtering and working on data that is local with respect to some trait of the agent. Local could mean physically local to the agent, or it could mean data that is local to the agent's purpose. In the first sense, data localization is very easy to imaging. A simple example is a set of agents meant to spider about the web and build a map of it. Each of these agents should use the data that is physically located locally so that the network resources of the Internet are efficiently used.

In the second meaning of data localization, we could insert data filtering instead and it would apply in most cases. Consider a set of agents that are to spider about the web and catalog it by topic. It makes sense to say that linked sites will have some correlation with each other by topic most of the time and so each agent will tend to work on one topic. Data localization is best realized when an agent working on filling out a category, let's say cooking, and finds a web page that it would classify as a sales pitch for spices. Sales is clearly in a category separate from cooking (by this agent's judgement) and so is best handled by an agent that is meant to handle sales and trade. This data, in the hands of the current agent with the current goal set, is not considered local. It is foreign to the relevant information.

To complete this example consider three obvious ways to make the data local. One is to assign the web site to another agent that is handling related data. The second is to spawn another agent to handle the new web site. The third option is to make this web site local by expanding the agent's goal set to include cataloging web sites of this nature.

The idea of data localization is very important as it not necessarily filtering. Some data must be ignored but some data is important. Localization seeks to minimize the volume of data so that the agent is not overwhelmed, but not to the extent that the agent can not learn from the surrounding information. Again, striving for a physical world model allows for an easy environment in which to test application of both data localization and data domain.

As discussed a physical world model addresses two issues of concern for an agent system that would need to interface with the physical world. Also, a nebulous data set is available which must be intelligently filtered through and processed. A physical world model can also map to many other problems and offers a wonderful teaching environment.

To model the physical world in and object-oriented manner yielded a very basic topology consisting of three major objects. Each of these objects interacts with other objects in the world either on a peer to peer level, or on an inter-object level. Inter-object level interactions can by very dynamic or very static, as will be discussed.

The first object, defined is the world. The world object provides some level of structure to the world, but is, more importantly, directly involved with the passing of events between objects. It facilitates interaction between objects. How this is done and other services provided for object varies between the two dominant world models.

Having the world as an object means that it can be coordinated with other worlds. A world could also be, conceivably, an agent in and of itself, containing agents of it's own. Options of this nature are not dealt with here, but do exist.

The second object type is the world object. The world object is what the name suggests. It is an object contained in the world. It should make use of services provided by the world it is in and know how to use the world to talk with other world objects.

The distinction between data and agent is not made here, but both are considered world objects. By this relationship, an agent can conceivably be data. This opens the door for the possibility of intelligent data. If data knows that it has been examined, then it can contribute to the problem solving. Data could also be constructed to be an agent that clusters itself with like types of data. This would give some order to the data allowing other agents responsible for processing it to work more efficiently. The idea of intelligent data is also not explored very deeply here, but is available by the peer relationship between all world Objects.

Dealing further with data objects, they can be of many forms. There is a very loose definition for them, and they also should be relatively lightweight in terms of processor requirements. All data would need to do is provide correct interactions with agents that are processing them.

Data objects should not yield a heavy processor load (when compared to an agent) because of the event model. The event model used for this system defines events as the third object. Events have in their definition an effect that they will have on an object that receives them. Consideration must be given for events that must travel over a medium of some sort. For example, if an agent was to simulate verbal communication, the strength of that transmission should decrease over physical distance. Processing of a received verbal event would consist of distance being processed and the message being put into some sort of buffer which the agent could look at. This adds up to very simple math and a string copy function.

Should a reply from a data object be required, the event generated by the agent would contain in it a method, which would construct and transmit a reply. Because of the nature of most data, only observation events are expected. More complicated events are expected to be sent between only other agents as they coordinate work or function on some higher level.

An event has in it also a pair of addresses. One is the source of the event and the other is the destination. This addressing information is used by the world to route the event to the intended object. This is meant for reducing processor load by avoiding event transmission to uninvolved world objects. Consideration should be given to having other objects be privileged to passing information. Casual observation might be a good way for agents to keep tabs on one another. It should also be noted that multicast addressing was not looked at in this research. Techniques used for handling Internet traffic can be applied to both world models.

There is also the matter of an event occurring not to an object, but to an area. The method used by this research is to create an world object that all world object know is an area event producer and have that event set off an event that is affected by distance. This event would be broadcast to all world objects, and only those in the effected area would process the event. All other object would drop the event. An alternate technique could be to have the world generate an event and avoid the formal placement of an object. These are all tasks for the programmer to consider and are all possibilities given the Sadwoja API. By the model used for this research, though, it is preferable to have an object set off an event regardless. The standing rule is that events come from objects, data or agent. To keep a solid model, this rule should not be broken, although it can be.

Events can be persistent or instance events. Instance events are the simplest type of events in that they occur at one instance in time. There is no discernable duration, as far as the involved world object is concerned. An instance event is something like stubbing your toe or breaking a glass. Such event can be broken down into smaller events, but it does not gain us anything. For a human being, stubbing your toe is an event that occurs at a point in time, not over duration of time. There is a gray area here that the programmer must distinguish per problem.

Persistent events are those events that take place over a period of time. Events such as eating take enough time so that another event could alter the occurring event. Consider a person walking to the store. If persistent events were not dealt with, our person could not receive or handle the event of being stopped by a brick wall until the store had been reached. You can see how ludicrous this situation is and so persistent events are very important.

One method used to deal with persistent events in both world models is by event recording. What first happens when an object receives an event is that it will update any persistent events that are pending in it's Persistent Event Record. The incoming event is processed and checked if it is persistent. If it is persistent, then it is added to the Persistent Event Record. If it is not persistent, then it is finished effected this object and is discarded.

The way that persistent events are updated is by time since their last update. The time is handled internally and only an update method should have to be called. When a persistent event finishes, it is removed from the Persistent Event Record. Persistent event termination is checked for immediately after the persistent event is updated.

As a side note, Sadwoja uses a method which returns whether the event has been completed or not to deal with persistence. If the event has not completed, it is added to the Persistent Event Record. If it has completed, it is discarded. There is no formal distinction between persistent events and instance events. An event is has either completed or it has not.

The active cell model defines the world as a set of cells that contain world objects. Each cell is connected to a set of other cells. These cells form an undirected graph that makes up the world. A simple example is to visualize a checkerboard. Each square is a cell and each flat side is a connection to a neighboring cell. Each of these cells corresponds to a physical position in this world. Each cell can contain zero or more world objects. Moving between cells is equivalent to moving in the physical world. Events must travel along these paths as well.

The individual cell is the base unit of the world. I should contain a list of all objects that are in it at any given point and make available connections to the cells immediately adjacent. Relaying to other cells is the key of the active cell's role. The interaction between cells is what binds the world together as a whole. If there is poor cell interaction, the world as a whole could suffer.

To ensure that data moves quickly between each cell, each cell should be it's own thread or process. This allows for the world to be spread out across several computers. Should the cell implementation ever be used, it is wise to put as many cells as you can on one machine. They are should be, individually, a light processor load. Should any parts of the world be distributed across two machines it is wise to do this at choke point in the world to minimize the potential of passing information over the network.

Passing a world object between cells with in a program is not very hard, but passing one between processes and computer is a little bit harder, which is why it is good to avoid it if possible. A world object is stored in this model with no id. An object is identified by which cell it occupies. Therefore, if two objects occupy the same cell, they are existing in the same space. Our laws of physics do not allow for this, and neither should this model. Rather on object should be allowed to occupy any cell at any time. Because only one object will be in each cell at any one time the cell can be used to identify the object. Events should be addressed with only the path to the object. The address of the sender can be found simply by retracing the path in reverse.

World object movement between cells should be instantiated by a movement event. This event should be targeted at the object in the cell. The payload for this event should be a set of instructions that will move the world object to the next cell and checking if the cell in empty. The case for generating events for other object to receive, updating them as to a moved object's new location is very debatable. On the one hand, it generates more traffic, and may give agents more information than they need. On the other hand, not telling other agents that a cell occupant has moved can make tracking difficult. There are good arguments for both and the final decision should rest with the programmer as per the problem requirements.

World Event Generation and Handling

Generating an event in this world model is very simple for the world object. All that needs to happen is that a constructed event must be handed to the world for distribution. The interesting things about the active cell model come in here. When a cell receives an event, it must handle it either as a directed or undirected event. Another way to describe the event as either addressed to a cell or a broadcast. Once the event is classified, it is handled by the cell.

A broadcast event has an alteration performed to it for the distance it will travel, and then that copy of the event is passed to all the surrounding cells. In the second hop (and all subsequent hops) the source cell should not have a copy of the event sent to it and the receiving cell should not duplicate this event if it has already happened. For example, it is conceivable to have a set of cells that go in a circle. If a powerful enough event is generated and broadcast then it could travel around the circle in two directions. The cell the first receives a second copy of the broadcast event should not handle it, but rather drop it. Other wise a lot of duplicate events will be received.

The purposed solution for this is to have a system to sign out event ID's that are unique to the scope of the world. This will keep events from conflicting and the id can be pushed across the borders of processes. If the world was contained within a single process, then there would be no need for unique id's as references could be checked against recently seen events.

There is also the exception of a reflected event. In the course of an event's propagation, there may be a reason for it to move back to a point where it has already been. Should an event be reflected it should have it's id changed so that it is recognized as a new event.

Directed events, however, are very simple. Because all of their addressing information is in the form of a graph path, they will navigate with out a problem and effect only the targeted cell. There are variations on what directed events can and should do, but this is the simple directed event. Note that world objects are always referenced by their relative position to the referencing object. If there is a need for unique ID's, that functionality should be added by the programmer.

When the target cell is reached, there is no one else to pass the event onto and it is given to all the objects that are located in the cell. These objects are responsible to handling the event appropriately. The world objects should be allowed access to all the information of the world event and should ignore parts that are either irrelevant to the event, or are deemed by the programmer to be secret. An example of secret information should be the return path to the sound made by a hidden animal. True, some indication of location should be given, but the exact return path to the hidden creature may be something that the programmer wants obscured.

Persistent events in these models can conceivably be of two types. The first is a persistent event, which effects an area. This would require the cell to store the event and play out any actions that it is responsible for on resident world objects. This is not a terribly good model as all events have sources in the physical world.

The more appropriate model for the object-oriented world is to have persistent events handled by objects and almost deny that there is a formal world structure handling the interconnections. In this model persistent events can be handled as they are in the general overview. The object will record the event and process it when other events come in. This makes for an adequate event model and brings events down to the world object level.

The growth of a broadcast event in the Active Cell model with out pruning is a geometric series. Without pruning, events can travel to nodes that they have all ready visited creating and echo effect. As previously stated, these echoed events must be dropped. This dropping of events will result in a substantial gain in efficiency.

First consider the naive approach where no pruning is done. This computation will be accomplished by taking each cell visitation to a cell, and mapping it to a single node in a tree. Thus, if an event is received by cell A, sent to node B, and finally sent back to cell A it will result in 3 nodes in the tree. This will result in a tree with the source node being the root and the branches per node being equal to the number of cells adjacent to each cell in our example. For this example let d be the distance that a broadcast event will travel before it is exhausted (and subsequently dropped) and let b be the number of cells each cell is adjacent (or connected) to. For this example b will be 4. An event with d equal to 3 will result in 85 event receptions of the event by cells. This is found by applying the formula NA = (bd+1-1)/(b-1) where NA is the total number of cell visited. This is the closed form of NA = bd+bd-1+bd-2+...+b0.

The Router World Model stores world objects in a vector with information about their physical location. The function of the world is to relay information. It very much functions as a router of information between world objects. There is also a broadcast mode that should be implemented. Each object should be assigned a unique id so that the world can address individual objects. The world should be the authoritative source of the id numbers.

Unlike the Active Cell Model, the Router model's data structures do not posses any information about the physical location of world object in the world. While this allows for having a much larger world, capable of sustaining a few objects over a large distance, it also means that all location information must also be simulated. This is the trade off between the two world models. There is no need for simulating location in the cell model, but it will produce a large amount of overhead for larger worlds, or worlds of finer granularity. In the case of the Router World Model, the size of the world should make no difference in computation time, but the number of objects will greatly increase the processing time regarding broadcast events and area affect events.

Recall the discussion of the cell receptions needed to propagate a broadcast event a distance of 3 cells. In the router world there is no distance factor that changes computation time. Rather it is by the number of objects in the world. Should any world object generate a broadcast event all world objects will have to be given a copy of the event. This requires some math to be done to see if the object is within range. Depending on how location is denoted by the system, this can vary the time needed by a constant factor of the time it takes to run through the list of objects.

As was shown earlier, computation requirements grow rapidly in an Active Cell world. Computation requirements for the Router World model are much more linear, and depend on the number of word objects in the system at the time. For large and diverse sets of data, the Active Cell model may be better suited, but does not readily offer a large world for movement. The Router World model offers a very large world and a relatively large size of agents with a lot of space. The abstraction of location also allows the world to be run in n-space with no major computation increase. Again, since location is computed, it is a constant factor increase. Adding another dimension to the Active Cell model would increase computation for broadcast events by order 1. Note that these computation analyses are all for broadcast events.

Looking at directed events, it is questionable which system would perform better. Time to deliver a directed world event to a world object in an Active Cell environment depends on the distance and path taken to the world object. A directed event is sent to its intended target by following directions. For example, if the target object is one cell to the left and two cells north, then the address would be left, north, north. Some shorthand and optimization can be done. If world cells are distributed across a very large network with inadequate bandwidth, relaying an event could take some time. The benefit is that the Active Cell model is highly distributable.

To send a directed event in the Router World model, first it is important to understand how the world talks about world objects. World objects in the Router model are generic world objects that know how to handle a world event and have a unique ID, which the world assigns. It is by this id that events are addressed. Because the path to the object is not used the id of the world object generating the event must also be included. When the world receives an event directed to another object, it looks that object up, usually in order n time, and sends it the event. Because to world assigns the id to the world object, the world can use a pattern of assignment which will yield a very effective hash table. This is an optimization that the programmer may wish to pursue. Other more simple optimizations may be using two data structures for objects, one with even numbers and one with odd numbers. This will speed up look-up times by a factor of 2 on average. This may also be desirable as two threads could be used to send out broadcast events to each set of objects. This would utilize two processors (if they were available) and could also speed up broadcasting of events.

In the Router world, since location is not represented by the data structures used it must be simulated. This also means that area directed events must use a work around. The method purposed here is to make an object which will not interact with other object (in other words, will drop all events) but will issue a broadcast event with a restriction on distance. Before an event is applied to a world object, that world object applies the distance from that event's source. The resulting event will reflect the distance in a reduction of effect, a garbling of the data payload, or even reducing itself to a null event (an event which does nothing).

This is a more computation heavy event because distance must be applied for every object in the world regardless of location. Location, again, is not defined here, but is up to the programmer. A cumbersome representation of location could result in a very slow system. A possible trade off would be to have the world objects do their own computation rather than the world doing the computation for them. This would require location information being included in the event. If the world objects are running over a network and are aware of their location, they may be able to do this computation. Note that it is possible for a distributed world object to never actually know its location in a world. The world object could triangulate its location through observing distances to other objects, but it is explicitly not needed.

In final analysis, the Router World model does not offer the clean functionality or the extremely high distribution of the Active Cell model, but it does offer what seems to be significant performance increases and a level of abstraction which is not available in the other model. Many of the distribution advantages of the Active Cell model can be had by the Router World model by segmenting the world into a mega-cell. It is perhaps more appropriate to not say that the Active Cell model is not suited to this system, but rather it functions best at a different level. Thinking of worlds as mega-cells allows for a much higher distribution with not nearly so much overhead in computation and coordination.

A good way of thinking of this idea of mega-cells is to consider two cities with a road between them. The cities can share information and resource if needed, but most of the activity goes on within the city. This goes back to the idea of data domain and data localization. The data domain would be both cities, but because of data localization, there is no great need to use the road linking them. Apply this to worlds and world objects and you can have a very large system with a lot of information running around in it distributed quite evenly between many computers.

Sadowja is meant to be a set of Java classes implementing the Router World model. The focus is versatility and ease of use for the programmer in implementing AI driven world object of various natures. While the system is meant for agents in its thinking various automatons can be let loose in a Sadwoja world, using various AI techniques. The Sadwoja libraries, though not tested fully, may also yield a friendly environment for students to implement various versions of AI solutions to problems, and have those solutions played out in an arena, or sorts. Use of Sadwoja classes is unrestricted in version 1.0 and all documentation is freely distributable.

The class structure of Sadwoja is very simplistic with the exception of the world objects. The world is a simple class that forwards events to world objects it knows about. The API is documented and performance of the world is very predictable.

The n-space classes implement some primitive vector routines providing locations and movement in n-space. The class NPoint is used to simulate location for the various world objects. This location is used to navigate around the world and also to determine distances over which events travel. Many events that travel over great distances weaken, and eventually become null events, events that do nothing.

The WorldObject class is the basic world object. If the entire system (world and world objects) is to be self-contained, then this is the basic class that should be used. Should load distribution over a network be desired, then there are two child classes of WorldObject which must be used. They are ObjectClient and ObjectServer. ObjectServer is a minimal representation of a WorldObject that will reside on the server while ObjectClient will connect to the ObjectServer and provide responses to all incoming events in the form of other events.

The real heart of the system resides in the WorldEvent class. A world event class is a generic template for specific events to be made from. All events in this world must extend WorldEvent. In doing so, they must implement methods specific to their task. This includes declaring when they have finished running and when they must alter the traits of a WorldObject appropriately. All communication is done via events. WorldEvents are serializable objects, and thus are pushed over the socket connection from the ObjectClient to the ObjectServer and back again.

There is also a Traits class that contains basic information which may be found useful to general uses of Sadwoja. The Traits class is nothing more than a set of public data that WorldEvents know how to manipulate. In the traits class is also contained an instance of NPoint to represent the location of the WorldObject. Other information that a programmer would like to include should be packaged into a class that extends Traits. There should also be written appropriate WorldEvents to handle that new data.

Perhaps the most thorough way to understand Sadwoja is to understand the flow of a WorldEvent. Consider a World instance, and in it are three WorldObjects. There is the WorldObject book, which is a small piece of intelligent data. There is also Bob a Java agent with an obsession for good books. Finally there is Marlene, who is completely uninterested in the book, but rather is more interested in observing the actions going on in this World so as to report the behavior of our book-loving agent, Bob.

What will first happen is that Bob will want to look around the world and so issues a Look event with a range of 90000. The range is arbitrarily large for this example. It should also be noted that at this instance range is not taken into account in Sadwoja for ranged events. This code was removed during an upgrade and has yet to be reinserted. Getting back to the Look event, Bob issues this event by constructing an instance of the Look class. This class is then passed as a parameter to the world by the method act. Since this is a network connection the method act is overwritten with one that sends the serializable WordEvent, Look, to the ObjectServer. Once the server has the event it will call the method sendEvent on class world, passing the received WorldEvent as a parameter. The event is then distributed to all WorldObjects. As a side note, this is a point of major inefficiency for network use, but less processing needs to be done by the world. Sending the WorldEvent to the ObjectServers is easy as it is done by calling the method handleEvent. This method, like act, is overridden by the ObjectServer's version of act, which will push the serializable WorldEvent out to the ObjectClient it is intended for. In the case of the Bob looking for object surrounding him, both the book and Marlene will receive a Look event. When the ObjectClient receives this event, the WorldEvent method effect is invoked with the ObjectClient as the parameter passed. The method effect is abstract in WorldEvent and must be defined for each extended class if this system is to work. This allows different events to carry different data payloads and still be treated as WorldObjects. The payload of data in these WorldEvent must be serializable to be pushed over a network socket. If they are not, then the programmer is stuck writing the model in one program.

When an event is received, it also results in the WorldObject notifying all objects waiting on it. Since only upon event receptions are persistent events updated, and only on event updates or receptions does data change, much busy waiting in which data is needlessly checked can be avoided. It should be noted that persistent events are updated before the incoming event is processed. Only after both of these steps are accomplished is notifyAll called on the WorldObject.

Any type of AI should be easy to patch onto this system. AI should contain an instance of a WorldObject or an ObjectClient and use them as gateways to the information in the world. All WorldObjects keep a record of objects that they have received Describe events from. Describe events are a response to the Look event. These records can be accessed by list index or by the id assigned by the world. By this a piece of AI can navigate this world and direct the WorldObject by creating events and calling act on the WorldObject.

Looking back at the example of Bob, Marlene and the book, in response to Bob's Look event both Marlene and the book will issue a Describe event carrying a copy of their traits back to Bob. When the effect method for the class Describe is called the traits and id of Marlene and the book will be added to Bob's List. The AI controlling Bob can now look through the list of known WorldObject and decide to act accordingly. If Bob is bored the AI may direct Bob to read the book. Since Marlene is around watching Bob the AI may direct Bob to do something more constructive. The AI may also try and pick between these two options by calling a special WorldEvent that a programmer made for dealing with the book where the tile is returned (though this could alternately be embedded in a custom instance of traits). The AI could use the title of the book to decide if it would be recreational reading, or work related reading. Bob's AI does not want Marlene running off and reporting that Bob is reading for recreation during a Sadwoja test session.

As previously stated, the exact nature of the AI driving a WorldObject is left up to the programmer. While Sadowja is designed to offer agent-like activity, it is also a very good environment for testing various implementations of AI solutions. Extending classes is very highly encouraged so that the general structure can be molded to suit a more specific need. There is a caveat about overriding classes that are not abstract. In these instances the programmer had better know what they are doing or the class may not perform exactly as expected.

Sadwoja offers a single world solution, though it is conceivable to set up some protocol for moving WorldObjects between discrete worlds. Such an optimization may allow for object training in one world and the moving into another world. Permissions could be applied to each world to more effectively map problems that have public and private information involved. The possibilities are very open, and that is the intention of this application. It is still under testing and should be used with the knowledge that it is very beta right at the writing of this paper. All are welcome to use Sadwoja for whatever purpose they find for it.