Designing the City

The actual city housed about 50000 people and was too large for us to recreate in full scale. We selected significant buildings and made accurate copies of those based on the results of archaeological excavations. Below you see the 3-stage process of translating the sketches from archaeologists into 3D models.

Virtual Humans in Uruk

To be able to simulate the ancient humans I had to implement many fundamental A.I. techniques. In an unstable and heavily distributed environment like Second Life, it was a rather difficult task. The key problems are: communication lag, packet loss and overall unstable nature of Second Life.

When you visit Uruk you will find a number of different agent groups there, each with different abilities. All of them are able to communicate with the users via instant messages. Some can do it better than the others. The largest group of agents are performing a random walk around the city centre. Those agents illustrate obstacle avoidance, crowd simulation, agent communication and priority planning.

Four agents (FishermanUruk1, FishermanUruk2, FishermanWifeUruk1 and WifeUruk2) close to the entrance of the city illustrate the complexity of object use, static planning and overall agent communication ability. They can also use the virtual institution and the information they can sense in the environment to be able to demonstrate environment-, self- and interaction-awareness in their chat dialogues with human users.

The king agent (ImgurSin) shows how one can use imitation learning to allow non-technical experts to extend the conversational abilities of an agent by simply correcting mistakes in their dialogues.

The priest agent (Fisherman Svoboda) pretends to be an oracle of Uruk and has all the answers to all possible questions. He employs an intelligent combination of web information retrieval and ALICE chatter engine to reply to user questions.

Finally, the pot maker “Koko Karsin” and the spear maker “SlaveUruk1 Braveheart” are capable of dynamic planning. They know about their state in the environment and continuously generate new goals. Via dynamic planning they can compose a sequence of actions that leads to the goal from the current state of the world. They can also correct themselves if their understanding of the current state is wrong (e.g. we deliberately delete the water pot every so often, so that the pot maker shows how he can persistently try to reach the goal by recalculating the plan with an updated knowledge).

Obstacle Avoidance and Locomotion

Obstacle avoidance is a fundamental technique for any embodied A.I. project of such kind. Agents must be able to get from point A to point B without being stuck somewhere in the middle.

Second Life doesn’t offer any obstacle avoidance solutions and it proved to be the most challenging part of the project. There is no possibility to track collisions on the agent side, the network lag forces the developer to develop synchronisation algorithms, packets can be lost, so you can’t be sure if you agent really is at the desired position and whether you really have accurate information about the obstacles in the environments. The physics system causes precision problems (e.g. the agent is directed to the position (x,y,z), but results being pushed by gravity and other forces to some other position) and there is no control over this process. 

Another big problem was that Second Life has its own unique way of storing the objects on the server. It’s unlike anything else in 3D graphics as they have to deal with severe optimisations. None of this was documented and it took me a VERY long time to figure out how the objects are stored.

Despite all those problems we implemented two classical obstacle avoidance algorithms: A* and Artificial Potential Fields. Potential Fields seem to work much faster than A* and that’s the algorithm being used in all the agents present in our region. With artificial potential fields for their locomotion the agents attach artificial emitters of repelling forces to all obstacles in the environment and use these forces to avoid collisions while moving between different positions in the environment. Those forces are not attached to the actual physical objects, but are simply calculated with the help of the navigation map.

The information about the obstacles is not hardcoded, but dynamically obtained from the Second Life server, which means that my agents would be able to avoid obstacles on pretty much any desired region.

You can learn more about obstacle avoidance for Second Life here and here.

Crowd Simulation and Group Behaviour

To simulate humans walking around the city, our agents perform a random walk. They use their dynamically obtained navigation map to randomly select a collision free location and then walk there avoiding the obstacles along the way. The agents can dynamically sense the environment and if they detect another agent at close proximity they might stop and initiate a conversation with them. They also perform occasional random gestures and animations every so often.

The agents can also sense danger (i.e. a donkey cart moving close to them and will often try to run away from it) and can also praise the King when the king is sensed nearby.

They can perform various group activities. One of those activities is a prayer. The prayer is announced by the city priest and all agents start running towards the temple and then pray. They have a number of plans, each for handling a different type of situation. Each plan has a different priority, which gives them the ability to decide that the prayer is more important than a random walk or chat with a friend.

A demo video that focuses on crowd simulation can be found here.

Agent Actions

The actions of the agents include: (i) chat messages that they can exchange with human users; (ii) institutional illocutions that they send to the institutional infrastructure or to other agents with the goal to change the institutional state; (iii) actions performed directly on the virtual environment that are not related to the change of the institutional state, including locomotion, playing an animation or performing operations with objects. Both illocutions and virtual world actions are essentially represented in a text form, where every action performed upon the virtual world is a request packet being sent to the Second Life server.

Gestures and animations are the most frequent actions performed by agents in the virtual world. There is a standard set of animations provided by Second Life, but custom gestures are often required too, i.e. pulling a jar with water from the well, lighting a fire, or spear-fishing. In such cases we employ a full body MVN XSENS motion capture suit that enables capturing a particular movement and importing it into Second Life.

Complexity of Object Use

In order to convincingly simulate the daily life of the ancient people it was important to enable agents to use objects in the environment (i.e. take a spear, jump on a boat and go fishing). Intelligent object use is one of the aspects of A.I. that hasn’t received appropriate attention. We have implemented a fully-fledged solution to object use for the heritage context. We have developed a designated library that provides a set of classes allowing agents to identify an object in the virtual world, attach it to the default attachment point, play a certain animation (i.e. rowing) associated with a given object, wear an object that is a piece of clothing, detach the piece of closing, drop an object to the ground and detach the object and hide it in the avatar’s inventory. All those classes take into account synchronisation issues and packet loss.

Below you see an example of how advanced the object use can be (with agents moving on top of an object, having another object they brought linked to it and carrying additional objects in their hands.

BDI agents and communication

For the agents to be able to communicate with one another, with users and with some objects in the environment - I developed a fully-fledged BDI platform similar to Jack Intelligent Agents. It allows for all the standard features of agent-oriented programming offering C# classes for agents, events, plans, beliefs, goals and supporting the message communication, plan selection on receipt of an event, priority planning, etc. The programmers can easily express beliefs and beliefs and desires of their agents, decide on the types of events they handle and design the plans to handle those events.

Interaction with the environment

There are two parts of the environment the agents are involved in: the visual part rendered by Second Life and the normative part supported by Virtual Institutions technology. The agents interact with the virtual world by sending commands to the Second Life server through libopenmetaverse. Through these commands they are capable of moving around the virtual world, perform certain animated behaviours, perform commands on the objects in the environment and interact with other agents or humans. The normative part enforces the social norms on all the Second Life participants. Agents interact with this part by sending and receiving illocutions (text messages) to the normative system of the virtual institution (see below).

Agents can interact directly with both parts of the environment while the humans can interact only with the visual part. The normative part will mediate agents’ actions there and will block the actions that are inconsistent with the social norms expressed in the normative part. In the visual part the agents are capable of sensing the changes of the environment state, including the movement of the objects or avatars, new objects or avatars, actions performed by all participants, etc. In the normative part the agents can send and receive the institutional illocutions and sense the state changes resulted by these illocutions. The state of the visual part of the environment represents parameters like the time of the day, positions and transformations of the objects and agents in the virtual world. The institutional state corresponds to the set of currently active scenes and the state of each scene.

Static Planning

As a classical BDI agent, every agent in our system relies on a number of plans to satisfy its goals. A plan is a set of instructions that should be triggered in response to some event. In the case of static planning (examples of which you can see by observing FishermanUruk1, FishermanUruk2, FishermanWifeUruk1 and WifeUruk2) - this set of instructions is a static piece of code that doesn’t change. Static planning is useful for programming some routines that do not change and must be performed in an exactly same way every single time. Static planning is also much less computationally expensive than dynamic planning. However, the resulting behaviour often lacks responsiveness to the changes in the environment and variation. 

A demo video that focuses on agent actions, complexity of object use, interaction with the environment and static planning can be found here.

Dynamic Planning

In the case of dynamic planning the agent can sense its current state in the environment and can react to environment changes re-evaluating its current plan. Rather than having a complete recipe provided for every situation the agent can encounter  - the agent is simply given the list of possible actions and has to find a way of combining those to reach its goals. For making this task realistic, each action is supplied with its execution preconditions and postconditions. The preconditions define the state, scene and objects that the agent must have to execute the given action. The postconditions determine how those attributes will change after the action is performed.

Dynamic planning is an extremely powerful technique. For a project like Uruk it can help to reduce the volume of programming (as there is no need to explicitly program the agents, all that has to be done - is to encode all the possible actions and allocate pre- and post-conditions) and allow for very complex agent behaviours (e.g. agents that can run out of supply for their trade and will walk and search for multiple possible suppliers and trade with them). Having an environment that is dynamic and can change not only as the result of agents’ actions but also in response to the actions of other agents and humans is quite a difficult case for an agent programmer if there is no dynamic planning.

I only learned about the contest a couple of weeks ago, so in the current demo there are only  2 agents that are capable of dynamic planning (Koko Karsin, and SlaveUruk1 Braveheart). For each of those agents every 5 minutes or so we reset its state to default and generate the goal “/Rested”. This tells the agent that it has to rest. From its knowledge base (an xml file) the agent can read all its possible actions and then use them to find the plan (a sequence of actions) that leads to the goal. In the case of Koko Karsin the agent is only allowed to rest if it finished work (which is making a clay pot). Thus, its plan is: Rested = Add Water -> Make Clay -> Make Pot -> Rest. To show the dynamic nature of planning - the water pot is deleted after every 3 pots made. So, by attempting to perform Add Water the agent approaches the location where the water pot is supposed to be, will sense that there is no pot, will fail the current plan, update the environment state to “NoWater” and will create the new plan that will also have the Get Water action before Add Water. 

Here are the knowledge base files for both of the dynamic planning agents. You can modify those, send them to me and I will restart the agents to show you how those changes are reflected in their behaviour.

The planning knowledge base for Koko Karsin can be downloaded here.

The planning knowledge base for SlaveUruk1 Braveheart can be downloaded here.

Priority Planning

Each agent with either static or dynamic planning may have to pursue multiple goals simultaneously. To make this happen, we introduced 5 priority levels that can be selected for each plan. For every event the agent receives - there is a corresponding plan that handles this event. Before initiating this plan the agent will first verify the priority of this plan and if it happens to be the case that this priority is higher than the priority of the currently active plan - the agent will suspend the active plan an will activate the new plan for handling the incoming event. At present - user commands are given the highest priority, followed by the pray request from the priest. Next comes praising the king (the agent will fall face down when the king is at close proximity). Finishing work and resting are the normal priority plans. Finally the low priority is allocated to random walk and social chat with other agents.

Intelligent Plan Interruption

To enable priority planning we had to design a complex system of handling plan interruptions. For static planning agents we simply run each plan in a separate thread, then the plan scheduler pauses and resumes the corresponding threads depending on their priority level. For the case of dynamic planning we are able to subdivide the plan into atomic actions. Each of these actions is then placed into a stack that the agent reads and executes the actions from. When a dynamic plan is suspended - we terminate the plan, but leave the stack populated. To make sure the agent is in the right state - we fail the state update for the last action and add this action back into the stack.

Virtual Institutions

The Virtual Institutions technology (see more on this concept here) provides tools for formal specification of institutional rules, verification of their correctness, mapping those to a given virtual world and enforcing the institutional rules on all participants (both humans and autonomous agents) at deployment, creating a regulated virtual world.

The specification is expressed through three types of conventions and their corresponding dimensions: Conventions on language – Dialogical Framework, determines language ontology and illocutionary particles that agents should use, roles they can play and the relationships among the roles; Conventions on activities – Performative Structure, establishes the different interaction protocols (scenes) the agents can engage in, and the role flow policy among them. A scene is a logically independent activity that can be enacted by a group of agents. In Virtual Institutions each scene often corresponds to a particular space in the virtual world; Conventions on behaviour – Norms, capture the consequences of agents’ actions within the institution (modelled as commitments and obligations) that agents acquire as consequence of some performed actions and that they must fulfil later on. Thus, the Virtual Institutions technology helps us define the interaction protocol for all the specified scenes, relationships and role flow among the participants and norms of the society. An example of specifying the aforementioned dimensions is shown below.

At deployment, the specification is connected to the virtual world (or respective area, i.e. an island in Second Life) and the state of the virtual world is mapped onto the state of the institution. Having the institutional formalisation aligned with the virtual world drives the decision making of virtual agents controlling the avatars. Agents have access to the institutional formalisation and can sense the change of the institutional state and reason about the actions (both own actions and actions performed by other participants) that resulted in the state change. Hence, for an agent it makes no difference if it interacts with an agent or a human as the result of the other party’s actions can be sensed through the normative platform and interpreted on a high level using the specification.

While at the current stage of the system not all agents are connected to the institution and the humans are not fully integrated to be able to choose a social role and get embedded into the virtual Uruk society - using Virtual Institutions seems to be the only way of establishing such integration. We essentially want to be able to to have the student replace one of the agents and then pursuing the assigned mission. In this mission the student would have to be involved into complex interactions with other agents and those agents must help the student and correct his/her behaviour if it’s not in line with the social norms of Uruk. With Virtual Institutions this becomes quite a feasible task.

Environment-, Self- and Interaction-awareness

Surprisingly enough, the majority of virtual agents are not fully integrated with their environment in terms of their reasoning. Most of existing research in the area is focused on agents’ conversational abilities, use of gestures  and emotions, while providing the agent with a limited awareness about the objects in the complex dynamic virtual world, its own state in relation to the environment and ignoring the interactions of other participants with the environment. If we want to include the humans into the system and allow agents to be acting as their guides in the environment they must be quite aware of their surroundings. To illustrate the importance of integrating such features into agent conversations consider a scenario outlined in the figure below. Here a human user learns in a Virtual World about the history and culture of Uruk through controlling an avatar of Fisherman Andel. There is a clear task he has to accomplish (catch some fish) and this task involves interacting with virtual agents representing ancient citizens of Uruk. As shown in the figure the human isn’t clear about how to progress toward the assigned task and asks the agent (Fisherman Jigsaw) about his options. To be able to reply in a similar manner as shown in the picture, the agent must know its interaction state, its location in the environment in relation to other objects and avatars, its own goals and beliefs and interaction capabilities of the user.

In order to understand their environment the agents use the information provided to them by the virtual institution and also rely on their sensors in the virtual world. In our demo two fishermen are supplied with the ability to express environment-, self- and interaction-awareness in their conversations with users.

En example video highlighting the key elements of this awareness can be found here. The research paper describing these features can be downloaded here.

Attention-Based Gaze Model

For the sake of believability, our agents are supplied with a programming solution dealing with idle gaze behaviour. When the agents are moving around their gaze is not fixed, but is changing using the attention based model similar to the model presented in [this paper]. The agent would shift its gaze between objects and avatars depending on the level of its interest in those. It will predominantly follow the movements of avatars approaching the agent at close proximity.

Without a proper gaze model that agents would be always looking ahead while walking and their had would not move. In contrast, with our gaze model the agents continuously look around and turn their had in search for interesting objects, when such an object is found - the agent keeps the gaze focus on it until a more interesting object comes along.

Conversational Ability: the Priest and the King

(Imitation Learning vs dynamic information retrieval)

All agents can chat with human visitors on topics, related to the heritage environment, through the instant message and chat mechanisms provided by Second Life. In order to participate in a conversation our agents employ the ALICE chat engine based on the AIML language. Each agent uses a number of AIML files that represent what can be seen as a common sense database. Additionally to this database every agent is supplied by personalised AIML files that reflect on its personality and the data relevant for its role within the virtual society.

What I found through interactions with the subject matter experts on this project is that it’s impossible to make them correct the AIML files directly. On the contrary, they were quite happy to chat with the agents and correct any wrong replies as they go. In our demo the King agent (ImgurSin Kariunga) is supplied with the ability to update its AMELI knowledge base through learning from the users by imitation. For this to work you must enter the password (the password access can be arranged on request) after asking the agent “I want to train you”. After successful authorisation the user can correct any wrong reply to the previous question by typing “Learn, .....” and the agent will update its knowledge base accordingly.

Another agent that is different from the rest in its conversational ability is the Priest. In conversations with users the priest agent pretends to be an oracle that knows all the facts about the world. As a true A.I. oracle, for obtaining those facts the agent turns to the World Wide Web. He tries various intelligent question answering techniques, using online knowledge repositories and search engines to produce the response. If the web search doesn’t produce any satisfactory results  - the agent will use the AIML rules for constructing the response. Try asking the agent simple facts about the world as shown in the picture below. Notice how the agent can interpret “How hot is the Sun” as being about temperature and how misspelling “Ukraine” in “Who is the president of Ukrain” still produces the correct response. It is also pretty good with mathematics. Try asking the Priest things like: “What is 2% of 10000?” or “How much is 2+2”.

Note, that this agent is not currently being used for teaching the students as in his replies it often includes online user opinions. Such opinions may contain course language, so we apologise if you encounter any of it.

      

Sophisticated Imitation Learning on different levels of abstraction

(Adobe Atmosphere only)

A complex learning feature of our system that is (due to the lack of time) not yet translated into Second Life is the ability of the agents to learn from human experts on multiple levels of abstraction via imitation. This video illustrates how Virtual Institutions can facilitate imitation learning of autonomous agents through environment formalisation. While not yet present in Uruk, this type of imitation learning will become one of the key techniques for directly translating the knowledge from subject matter experts to the agents.

The developed prototype verifies the research hypotheses outlined in this paper. The methods of recursive-arc  graphs (similar to recursive decision trees) is used for learning user actions and assigning probabilities to those. This graph is then utilised by the agent in its independent decision making.

The demonstration video shows how an agent can select an appropriate sequence of actions, previously performed by the human teacher, based on the parameters the agent can observe in the environment. In this case the human was entering the virtual trading house an number of times, where he completed authorisation, went through the meeting room and joined the auction room. In his journey, depending on what and whom the user saw (through the view field of its avatar), it was performing the actions in a different way (e.g. seeing an avatar of an old friend normally resulted in approaching this avatar). Behind the scenes, the agent was observing an learning. The video shows how after some training the agent is left on its own an assigned a goal to enter the trading room. In pursuing this goal the agent utilises the probabilities assigned on the nodes of the recursive-arc graph (by following the most probable path leading to the goal) and uses the nearest-neighbour method for matching what it can observe to the list of recorded parameters the users was able to observe during training.

The live presentation of this feature can be arranged on request, but this will include installing additional software.

Project Evaluation

We are finalising an extensive users study about the Uruk project. In this study we separated our participants (university students) into two groups. The first group was reading a text document (with pictures) presenting them with the same information as what they would learn by interacting with our agents in the Virtual World. The second group was instructed to enter the city of Uruk in Second Life and interact with the agents there. Our study instructor was ensuring that they absorbed all the same knowledge as the text group would have.

Then we conducted a mini-exam with both groups. The results show that the group that learned in the virtual world spent much more time than it required to complete reading the text, but their exam marks were on average 20% higher than the results of the text group. We also received quite emotional positive feedback from the virtual worlds group, while in some of the text group responses we found a few sad smilies and some students explicitly told us that it was quite a boring experience for them.

Such results are more than encouraging!