AI in the World: Avoiding Traffic Jams

Here's a link to a story about Clearflow, software from Microsoft Research being used to model and avoid traffic jams.

The research is partially described in a Microsoft Research paper linked here.

In uncharacteristically logical fashion for Microsoft, Clearflow is a good example of taking an extremely complicated problem of traffic data analysis, and presenting it to a user as the solution to a straightforward problem: How should I get there from here?

The Clearflow system will be freely available as part of the company’s Live.com site (maps.live.com) for 72 cities in the United States. Microsoft says it will give drivers alternative route information that is more accurate and attuned to current traffic patterns on both freeways and side streets.

What's nice is it sounds like the interface will be exactly the same as using any old normal route planning software.

I'd like to know how much of it's traffic data is being pulled from some live source, rather than predicted through some model.

Selling AI to People

Let's say you're somewhere in the field of AI. You are somewhere from AI researcher (only uses their keyboard to check their mail, every 1 minute) to AI developer (fingers rarely leave keyboard). You know what AI is. AI is simply the automation of things, under various circumstances. There are certain laborious, dangerous, prohibitively difficult tasks, so we make software or machines to do them.

If you utter "Artificial Intelligence" to a non-technical person, a completely different image appears in their mind. It's something a bit more like this:

or worse, this:

I've actually had people ask me if machines will one day "love".

The non-technical person has a completely different image of what constitutes AI than you do. The consequence of this for the entrepreneur is, if you tell someone "My software is revolutionary because it uses Artificial Intelligence!!", they will undoubtedly become excited, and then become utterly disappointed when you actually show them your software.

No where have I learned this lesson more bluntly than when I was pitching my startup to a venture capitalist.

Brief story. This was back when our software was something completely different, and we were pitching it as basically an intelligent task management system. We walked into the meeting, and by this point, all the investor knew was it involved artificial intelligence, and he was very excited. As we were giving the presentation, you could slowly see the man deflate. When it finally came time to give our demo. He watched the system assign unfinished tasks to time slots, and exclaimed "it's just putting tasks where ever there's free time." I tried to explain that no, the system is actually sorting through many constraints, and figuring out what the possible orderings there are for tasks given the goals that have to be accomplished, but he was having none of it. "This isn't...artificial" he said in disappointment.

AI is about solving problems that are too difficult to do by hand. It enables you to solve extreme, prohibitively difficult problems. For example, finding content on the internet relative to your query involves looking at TRILLIONS of pages and examining them. One person could not do it in his lifetime, so Google uses AI to do it for you. But you'll notice Google does not ever say "We use AI! Come use our search engine!" They just solved a problem no one else could nearly as well, and let this fact speak for itself.

A similiar sentiment has been expressed recently by the infamous Ted Dziuba, one of the creators of Pressflip (formerly Persai), a new content recommendation site:

How Does it Work?

That's a good question. After dealing with angel investors, VCs, users, and anybody who isn't an engineer, the answer in my mind is, nobody gives a shit. Really, nobody cares about your algorithm or how revolutionary you think it is. All people care about is a system that shows them things they want to read.

I'm here to tell you, man, that is right on.

Your software is not revolutionary because it uses Artificial Intelligence. Your software is revolutionary because it is able to solve a problem that was until this moment not solved. *That* is what you must pitch.

Assassin's Creed: In game demo!

Whoa, in game footage of Assassin's creed during an onscreen demonstration. Check it out here. I'm sure you'll notice especially the large crowds populating the city. Pretty amazing, although there's no word on how goal-directed the crowd NPCs are.

Getting Speed with Inadmissible Heuristics

If you're here, chances are you've read about A* search. Just a quick review:

It is a state space search algorithm, that examines nodes in a space full of them. At any moment of your search, you've got a "frontier" of nodes that you may be immediately examining:

Associated with each node, s, is a cost of reaching it, g(s). You proceed with your seach by examining your frontier of nodes, and picking one that minimizes a criteria I will mention in a moment, f(s). You then "expand" s, meaning you find out s's immediate neighbors in this space and then get rid of it (remove it from the frontier), and then you stick those neighbors on the frontier list. Thus, the frontier list contains every node you have not expanded. A* is just a way of telling you, which one you're going to expand next.

So, right at this moment in the search depicted in the figure, the frontier is:

s1 G' n s2 s3

Of course the whole point of doing the walk through this space is to find a node that has particular qualities that you're looking for, i.e. a goal node. Multiple nodes in the space may actually contain the goal criteria, it's just that in doing this search you're looking for the path of nodes that gets you to a goal containing node optimally.

Back to selecting nodes on the frontier. The special thing to A* is in the function f(s) that you use to rank the nodes within the frontier. You select the next node on the frontier to look at using a best first search on the function f like so:

For each node s on the frontier, f(s) = g(s) + h(s), where g(s) is the measured (actual) cost to get from the start node to here (node s), and h(s) is the estimated cost of getting from here (node s) to the goal.

Now, if h(s) (the estimated cost of getting from here to the goal) is guaranteed to be less than or equal to the actual cost (i.e., h(s) is admissible), then you can make all sorts of guarantees about the outcome of the search process. Specifically, that A* is complete (if there is a solution, A* will find it) and optimal (the solution it finds costs the least to get to starting from the initial node).

What happens when h(s) is no longer admissible?

Well, let's see. Suppose you've got a frontier of nodes at some point in the search:

One of them is G', which as the goal in it, although suppose we known that G' is not the optimal goal. This means:

f(G') = g(G') + h(G')

Suppose that the optimal way of getting to a goal costs you C, i.e. the optimal goal G is such that:

f(G) = g(G) + h(G) = g(G) + 0 (because h(s) = 0 at a goal node) = C

So, regarding that suboptimal goal G':

f(G') = g(G') + h(G') = g(G') > C

If there is actually a path from the initial node to the optimal goal, then there must be some node, n, in your current frontier that leads you to the optimal goal. i.e., if you expanded n, you would find the optimal route to the goal in that sub tree. For that node, n:

f(n) = g(n) + h(n) <= C

if h is admissible. Thus, n has a lower f value than G' does, so we can see that A* always chooses to expand the path through n first (leading to the optimal solution).

If h is not admissible, then G' is still not the optimal solution:

f(G') = h(G') + g(G') > C

just as before. However, regarding that other node n that actually leads to the optimal solution:

f(n) = h(n) + g(n)

f(n) is not necessarily less than C. That is, if h(n) is an overestimation, then f(n) is definitely not less than C. So now you have both G' and n sitting in the frontier, and both are bigger than C. Thus, in general, an inadmissible heuristic means that G' can be selected before n.

This is not necessarily, bad, actually. If your heuristic is such that G' pops out of your search first, then although G' is not optimal, it takes a fewer number of steps to get to than the optimal solution G does. In cases where a shorter plan that works is prefered to a longer (but cheaper) one, this is just what we're looking for. What this means is if your heuristic is inadmissible and leads to G' before G, then it takes less time to compute the solution than it would for an admissible heuristic, because A* has to churn a little bit longer (by going through n) in order to discover G.

The moral is, if you're just looking for path to the goal quickly, rather than spending a longer amount of time finding the optimal goal, then perhaps it's worth it crafting an inadmissible heuristic.

In fact inadmissible heuristics have already been used to this effect in state-space planners yielding exactly this benefit. The HSP planner uses an automatically generated inadmissible heuristic to gain such speed. HSP was later advanced upon to become the FF (fast forward) planner, where it achieved its apex of coolness.

The Unique AI Space of Games

There are unique AI problems to solve regarding autonomous agents in virtual environments. I write about them in a paper here but I would like to elaborate upon some of them here. In general, when you're making an AI for an autonomous agent, it can be to automate basically any task. For example, a land rover, an intelligent display, or even simulating an entire city population. Within virtual environments, however, and video games in particular, AI is very often (currently most often) used to control a virtual human being.

This has several consequences for designing your AI, but only one of them is for planning. As noted in the paper, the virutal human-ness of your agent means that now, just any old plan that acheives your goal is not acceptable. Flying over a building will get you from here to there, but humans can't fly over buildings, so that plan is not acceptable. So simulating a human restricts the space of valid plans.

Something that occured to me recently, though, is that AI for virtual humans does not simply entail making a system to make P true given we are in a world in which P isn't true (i.e. a planner). To see what I mean, take a look at this Bioshock demo. (Check out the later parts of the demo too).

There's this cool part where the player approaches one of the resident creepies (a Big Daddy) who protects one of the little sisters. Normally, the Big Daddys go about their own business, and actually leave you alone if you do nothing threatening. If you approach one of the Big Daddys while he's with a little sister, he sort of grumbles and frightens you, and tries to continue on about his business. He doesn't immediately launch into an attack, he doesn't run away, he instead does something that exhibits personality.

In general, it's clear that there's a problem space between making a planning agent, i.e. being able to make a plan so as to optimzie some criteria, and a virtual creature, i.e. actually appearing to be a resident of a virtual world.

To PhD or not to PhD

As promised, following is some very insightful advice from the one and only Jeff Orkin on choosing to go for a PhD for anyone wanting to do AI in the game industry. I have certainly been struggling mightily with this decision recently. hi Don,

I'd be glad to offer you any advice that I can. Feel free to ask me questions about AI in the game industry.

I can give you brain dump on my thoughts about working as a "gun for hire", or for a game company, or pursuing a PhD...

The good news is there's lots of opportunity for AI specialists in the game industry right now. Pretty much every game company is looking for help in this area, and finding skilled/experienced people is hard. And none of the existing middleware fully does the job. Graphics guys are a dime a dozen now, and AI is differentiating one game from another, but AI guys are hard to find.

Deciding on the best career route to take depends on your priorities. Are you more interested in innovating, or making money? Do you want to travel much? Do you want to work alone, or be part of a team? Are you more interested in games, or technology?

Most game companies will require that the AI engineer works on- site, to work closely with the animators and level designers. I've only heard of one example of someone doing contract game AI from home -- after Brian Long worked for Monolith on the first No One Lives Forever, he left the company and worked from home on the navigational mesh pathfinding system for "Savage". I think it may have been hard to find additional contracts, and possibly lonely, so now he works for a dot com. It is definitely easier to find contract work with credit on recognized titles under your belt - so you might consider starting by working directly for a game company.

In general, the drawbacks of working as an external "gun for hire" are that you will not share in the profits of the game, and you might work on more isolated, less innovative stuff. I was able to innovate on the FEAR planning system because I had earned the managers' trust by working with the same team on No One Lives Forever 2.

Most games aren't very profitable for the developers anyway though, so you may not be sacrificing much in that department. It's a tough business, and publishers often rope developers in unfavorable multi-game deals before they have a hit. For example, FEAR was the end of a multi-game deal penned before the first No One Lives Forever, so Monolith saw relatively little profit on a game that sold close to a million copies for PC.

When you are "in the trenches" working for a developer, the demands of keeping up with bugs, designer requests, and the competition can consume so much of your time that it's hard to think about long-term innovation. I decided to do the PhD to get some new perspectives, explore some more far-fetched ideas, plus do some traveling and networking at conferences.

Eventually I hope to work with the game industry again, and apply ideas that I develop through research.

A PhD is definitely not needed to work in game AI, but there are a growing number of PhDs in the field now. John Hancock at Lucas Arts did a PhD at CMU. Ian Davis founded MadDoc after a PhD at CMU and then worked as CTO at Activision. Dr. Paul Krezewski founded AI.Implant. Former Media Lab Prof Bruce Blumberg now works at Blue Fang. Etc, etc...

Then there are also lots of academic opportunities for research with games, like obviously ICT, plus similar projects at Stottler-Henke's AI consulting firm.

I think my experience in industry has given me valuable perspectives to apply to my current academic research, ... but I also feel like a pretty old grad student. So, if you are going to do a PhD, you don't want to wait too many years to start -- but at least you've finished the masters.

Wow, this has gotten pretty long. Hope it's helpful!

jeff

Thanks Jeff!

Wandering Behavior for AI: Why and How

As I talked about in an earlier post, wandering behavior is an almost always necessary component of AI for any virtual, persistently populated environment.

Why Wandering is Important

To briefly summarize from the earlier post, the resource control (RC) model is a very popular scheme for implementing control of a virtual population. The gist of RC is, agents need resources, and their need for them increases over time. When the need crosses a threshold, agents seek out something in the environment that provides that resource. In this way, RC provides computationally cheap, reasonably realistic looking behavior. The essential problem is, then, how do agents find out about things in the world that satisfy resources?

Seeking: You could pre-load all the information about the world into a universally accessible dictionary structure of some sort. This way, when an agent needs some food, he queries the world for the nearest burger joint and goes there. Exploring/Wandering: Alternatively, you could tell the agents nothing, and then have them randomly walk around the virtual world finding things. Eventually, they find out where everything is, and the agents act just as they do in the first option.

For those of you who are into reinforcement learning, the second option should sound a lot like model-less Q-Learning. In Q-Learning, the agent starts off knowing little to nothing about the world, and through randomly sampling the environment, figures out what/where the “rewarding” things are. At some point, the agent decides to stop exploring, and starts exploiting its knowledge about the environment. If new information is constantly appearing in the world, however, you can’t ever turn off that exploring component. Thus, if the resource-bearing environment is always gaining/losing/altering resource values, wandering is always necessary. Wandering, in other words, is the solution to the constant appearance of new information (if not relying entirely upon Seeking, see this earlier post).

The Wandering Problem

The constant appearance of new information introduces two problems:

1. Finding out about the new information
2. Planning and acting based on changing data

When I say an agent performs “wandering”, it is equivalent to saying he has a (reasonably efficient) solution to these two problems.

The Wandering Solution

I’ll consider the first problem here, and the second in a later post. To consider how an agent should find out about a bunch of new information, let’s consider an example. You’re at a hotel, α, and you want to find a restaurant in the area. You don’t know where anything is, so you decide to take a stroll, and you’ll stop when you find something interesting. Let’s represent this scenario like so:

To “find out about new information”, one has to visit all the nodes, or a subset of them (until you’ve found a nice enough place to eat or something sufficiently distracting). The question is, is there an “optimal” way to visit them, and if so what is it?

First, the above picture can be resolved into the following graph to indicate which nodes (restaurants) are adjacent to each other:

In this graph, a solid line means the nodes are adjacent to each other (i.e. it makes sense for someone to visit F after visiting E. The dotted lines means technically, the nodes are adjacent, but whether or not someone would visit one after the other is up for debate. For example, L is adjacent to E, but it’s across the street, so a person might not really go from E straight to L.

The first thing off the top of your head when designing the algorithm might be to visit them in Depth First Search order, the outcome of which is:

α D E L K H J C I M B F G A

Is that the order you would visit the buildings in? I didn’t think so.

Clearly, any path of visitation is not satisfactory. One criteria to capture is the “naturalness” of the path of visitation. I suppose there are many possible definitions of a “natural” path. But for this post, I will hypothesize that a natural path of visitation is one that minimizes the deviation from initial heading. Slightly more formally, a path becomes less natural the more zig-zagging you do. More precisely:

A path of visitation for graph G = (E,V), is a string of nodes P = e1 e2 ... en such that ∀ei , ei ∈ E ei and ej appear next to each other only if they are adjacent to each other in G. en is a node at the periphery of G.
The deviation of a path of visitation P (in the depicted graph) is the number of horizontal edges traversed.

Thus, the deviation of a path is how “zigzaggy” it is. Just count the number of left arrows and right arrows in a given graph traversal.

Given this definition, a visitation path of minimum deviation (and maximum naturalness) is:

P0 ≡ α D E L K

which has a deviation of 0.

P0 is definitely natural, although it does not allow you to visit very many nodes. You might have a certain threshold number of buildings that you insist on visiting before making a decision. In this way, there is a second criteria to keep in mind: number of nodes visited.

Note that, for path P, the number of nodes visited by P, and the deviation of P are directly proportional to each other: Increasing the zig-zagging of P means that you will hit more nodes.

The agent designer must therefore solve the following problem. Given a certain minimum number of nodes the agent must visit, what are the paths of minimum deviation?

For the graph above, these paths are:

Nodes agent must visit	Path of minimum Deviation (cost)
4	αDEF (1)
5	αDELK (0)
6	αDEBHI, αDELHI (1)
7	αDELHBC, αDEBHLK (2)

More on the second problem regarding planning and acting based on changing data later.

The Resource Control Model and Wandering

When you’re creating AI to control a population of thousands of visualized entities, and it’s all supposed to run on one machine, your options can often be limited. Now, I know I said population up there, and a lot of you read that as crowd and you would be wrong wrong wrong. So here comes a brief but informative aside. The problems of creating realistic crowd behavior and population behavior are two completely separate things:

• Crowds: Smaller in scope, both in time (duration of gathering) and in size (i.e. hours or days, 10s, 100s, 1000s of people). Actions do not have lasting consequences (see below). An example of this is a bunch of people assembled around a car accident, or in a stadium to witness a rock concert.
• Populations: Large in scope, both in time and size (days, months, years, forever, population size on the order of 10^3, 10^4, or 10^5). In a population, one agent’s life is totally independent of another agent’s life: i.e. two agents in a the same place at the same time are most probably not there for the same reason, whereas the opposite is true for crowds. The most significant differences between a population and a crowd, however, is that a population itself has a personality, and actions have lasting consequences.

By this I mean the following. When modeling a population, now you have to think about modeling time-of-day events, such as rush hour in the morning and evening, and making food vendors more busy during the lunch hour.

In addition, if a traumatic event, such as an explosion, occurs at location L, then now you have to model the effect this had on the population. When people pass by L, now they’re creeped out by it a bit, or perhaps they completely steer clear of it. Now the city has a history, which the population itself makes and reacts to.

Now that that’s out of the way, we can talk about modeling populations. Actually, I wanted to talk about just one model in particular, that is pretty popular + successful: The resource control model, and some of the implications of using it for population control. Used in such places as The Sims, and Shao and Terzopolous, the resource model essentially creates agents that look for things when they run out of them.

In the resource control model, agents maintain a list of resources, including things such as hunger or satisfaction, often represented simply as a number. The resource value can be thought of as “urge for/to” something. Due to whatever reason, eventually the resource value will increase beyond a threshold, and the agent has to do something about it. For example, eventually the hunger resource will increase beyond a threshold. At this point, the agent examines the world for things satisfying hunger, i.e. places providing food.

Of course, the success of this framework hinges up on the agents being able to find what they’re looking for the environment. There are two things spanning the space of options:

• Directory Lookup: An agent can query the system for the nearest food stand. The system returns the location of the food stand.
• Wandering: There is no directory facility. To find out where things are, agents have to wander around the city, noting whenever it finds something interesting.

Any population control scheme using resource control will most probably use a combination of these two. If the agents start out with all wandering, and there’s no directory service, then as they note things, eventually the information will be put into a sort of directory. Agents that use only directory lookup become excessively mechanical. If the population only cares about things they already know about, then new information is difficult to propagate.

So, any combination of the above two axes has wandering as a component.

The question is: How do you do good wandering behavior?

Let me roll that one over a little.

AIIDE 2006 Notes

I got a lot of nice feedback from my presentation. Basically the main message I wanted to get across was the following. When you have a plan, and you want to actually start executing it in a real (or virtual) environment, the plan can at some point midway become broken, i.e. no longer possible to execute. The source of this problem is one (or both) of the following:

• Uncertainty (coming in three flavors)
• Dynamic Environments

Of the options that people have thought up (classic planning/execution/replanning, policy-based methods, and incremental planning), I argue that incremental planning is by far the best option in virtual environments for solving the Dynamic Environments part. So, ICT is excited about getting Incremental Planning to solve Uncertainty as well.

One of the questions brought up the point of using randomized policies to solve the “rigidity” of policies in MDP based models. This is definitely something that I need to think more about (although I did write an MS Thesis about it). Off the top of my head, though, I think the main questions to be answered regarding using randomized policies is

1. Is the reduced expected reward you got as a result of putting in randomization worth it?
2. Can randomized action selection be made to look believable? i.e. If I’m randomly committing actions, will it look like I’m a crazy person who in the long run gets to the goal?

First question: I suspect the answer is yes, depending on how much randomization you put in there, and if you know anything about your adversary. That is, the less you know about your adversary, the less you can exploit anything you know about him, and so simply acting more randomly becomes a better and better recourse.

Second question: ::shrug::

More posts about some of the other talks coming soon. Look forward to a discussion of the Sims 2 AI presentation.

On Making Up Stuff as You Go Along

I just finished playing Dreamfall: The Longest Journey.

First off, this game is awesome. If you’re interested in the story of the The Longest Journey universe, you will definitely find this to be a very compelling game, if a bit short.

I mention it, however, because games such as Dreamfall, Indigo Prophecy, and Shadow of Destiny are screaming for dynamically generated content. I mean this in the sense that is described in Story Director and Interactive Narrative technology in general. In the Story Director methodology, a story author has a sequence of dramatic points that he wishes the audience to experience. He might even have a specific, scripted plan for how the audience should reach those dramatic points. This is, of course, what is done normally in games. In order to make this work, however, the player is prevented from doing anything that really interferes with the story author’s plan, often in a totally unnatural way. By “unnatural”, I mean you see the following sort of thing:

• Totally fake characters : If the story line requires that the player meet with character X at location L, then X is waiting at L forever, until the player gets there. i.e., characters have no lives outside of talking to you. When they’re not talking to you, they’re waiting to talk to you.
• Artificially static environments : If a scripted path going from one plot point to another plot point requires character X to go through a doorway, then that doorway better be clear in order for the plot to continue. So now, you can’t have too many computer controlled characters walking around because they might be in the way, and you can’t have the building be destroyed or made inaccessible by the player accidentally setting an explosion off nearby

The result of all this is the human player is painfully aware they’re in a fake reality, and immersion is broken. To address this problem, Story Director technology retains immersion by recovering from an author’s plan made broken through unpredictable user interaction. It does this like so: The author specifies a list of important plot points that the audience must experience, and possibly an initial plan for getting from one plot point to the next. If the user does something that breaks the plan, then a Story Director creates a new plan, that meets the same plot points.

This makes the following situation possible. Suppose you (the player) are about to meet an informant in an alley way, to get some vital information so that the story continues. Upon getting there, the two of you are jumped by some thugs. For some reason, you fail to act quickly, and your informant is killed, before telling you the vital info. Now the system recovers, and finds a new way to get that information to you: The informant’s brother/girlfriend/wife/boss/pet panda sends you a letter, or you have to track down the informant’s sources yourself resulting in a whole new section of the game opening up.

Now your actions have consequences. Now your actions have meaning within games in virtual worlds.

Can game designers tackle the prospect of run-time generated story content?