Artificial Intelligence Depot
Visiting guest. Why not sign in?
News, knowledge and discussion for the AI enthusiast.
FEATURES COMMUNITY KNOWLEDGE SEARCH  
The Elements of Statistical Learning
Describes important statistical ideas in machine learning, data mining, and bioinformatics. Covers a broad range, from prediction to unsupervised learning, including classification trees and neural networks.
More information at Amazon US UK

Reply to Message

Not registered yet?

The AI Depot has a focused community of friendly users. Rather than let anyone abuse the site at the brink of promiscuity, we prefer to let only those with an active interest participate... this simply requires registering.

Why not sign up!

Joining the site's community is completely free. You can then post messages freely, and customise your personal profile at will. Specific privileges will also be granted to you, like being able to access printer-friendly articles without restrictions. So, why not register?

Username:
Password:
Subject:
Email me when someone replies.
Body:

Parent Message

pathfinding is used more often for other purposes than movement

>it works with incremental updates to the state which

>converges to the right result. Since movement is usually

>very small, you can take advantage of a strong frame to

>frame consistency anyway

This is a nice design. Be aware however that in a full blown game AI application, the largest customer of the pathfinding system is not the 'bot movement AI' but the goal evaluator. This goal evaluator frequently evaluates the best course of action, which typically is about:

<ul>

<li>am I healthy and is a health powerup nearby</li>

<li>does it make sense to pursuit a threat that went out of sight</li>

<li>which is the best weapon to pickup, given their value and distance to the bot</li>

<li>what should I do: defend the base, attack the enemy base, escort the flag carrier (typically based on the distance to the base and carrier)</li>

</ul>

Most of the goals the AI might adopt have a value that depends on the (travel time) distance to some object or location. Without at least a very good cache and caching strategy, any dynamic path finder will become the AI's bottleneck.

For that reason, and for performance/frame rate, and for simplicity, most FPS AI simply uses path lookup tables rather than dynamic pathfinding (like A*).

Table based path lookup tends to be 200 times faster than a heavily tuned A* implementation. In other words, for the same costs of computing a single A* path, the AI could have retrieved and compared 200 static paths. That will give you some time to check and deal with the occasional exception (pre-computed path is blocked, so I need to fall back on an A* dynamic pathfinder for this particular path).

William

19 posts.
Thursday 07 March, 14:23
Reply
Caching

The whole thing is essentially a cache. Goals may be reused often over the course of the game, but they are not usually changed at small intervals. Though the algorithm on default settings can produce satisfactory results within 1 logic frame, but it's acceptable to take up to 0.5s to make such a decision. When the higher-level AI sets a goal, it increases the reward for a node. The chosen path then iteratively converges to the most optimal -- if no noise is added.

Short paths do not need to be cached since rewards can be combined. You set the reward for a closer item, and the path to the furthest reward node will take the detour.

I can guarantee this dynamic path-finder will not be the bottleneck. Firstly, it can return after any amount of time. Secondly, it uses consistency and plasticity, which means estimates are updated as time goes by.

You can take advantage of it fully by voluntarily adding dynamic conditions, otherwise, it'll just converge to perfection.

Alex

935 posts.
Thursday 07 March, 20:46
Reply
path lengths, not the paths

Alex, thanks for the reply and clarification.

I'm not sure we're discussing the same problem. My statement is that when you complete your AI into a full blown game AI, the main demand for paths is about path lengths, not the paths themselves.

Full blown bots will spend much of time (and code) in considering alternatives (should I take cover, attack, get a power-up, get the flag, camp here, join up with teammate x,y,z, etc.). Nearly every evaluations of such alternatives requires 'distance' information: is there any cover available with 2s distance, can I get to the threat quickly, is there any power-up nearby, who is the nearest teammate, etc.
In evaluating the alternatives, the exact path does not matter. Only when an alternative is chosen, the exact path is retrieved.
In other words, what the AI really needs is a (very) efficient way to estimate distances between his position and (almost) arbitrary locations on the map.
An AI design that is purely based on dynamic pathfinding (such as A*) will not be very efficient at these distance evaluations. Something closer to lookup tables and caches is required.

Your design sounds very interesting, and it's the first time I've seen concepts like plasticity being used. You also address the problem of optimizing a path towards multiple goals (TSP like).
But from what you describe, I cannot tell whether it is aimed at rapid pathfinding or rapid distance lookup, or both.
Do you have any numbers for "Firstly, it can return after any amount of time" (which I assume refers to the algorithm's ability to provide early results, rather than an absolute time).

For reference, on a PIII/500MHz, I could do over 5,000,000 distance lookup/s, whereas I could do solely ~1,700 A* path searches. (The earlier posted difference between A* and path lookup was incorrect, and should be a factor 2,000, not 200).
This factor 2000 is the difference between freely estimating distances everytime and everywhere it is needed in the AI (implementation), and on the other hand introducing complex caching and a resource manager (with queues to handle excessive requests posted in one frame) for A* path lookup.
Obviously, standard path lookup tables become cumbersome once you have over 1,500 waypoints/areas/cells/...

William

19 posts.
Friday 08 March, 04:26
Reply
Speed Tests

The cache also has distance values (or travel-time, or cumulated cost), so the penalty for a query is simply an array lookup. I'm in the process of reducing the memory overhead for each node -- there's few nodes anyway, but every little helps.

I'm going to write a paper about it for the ICCG. I've no idea if this is the sort of thing they are looking for, but it's definitely a good opportunity to do lots more testing.

Cheers for the interest ;)

935 posts.
Saturday 09 March, 11:09
Reply

Back to the Artificial Intelligence Depot.