Hi I am working on a problem of finding a good tactical path for an NPC. By that I mean a path that is not in the line of fire of many enemies, and will bring the NPC within firing range of the enemy it wants to attack. Now I know this is a problem that has been dealt with before (e.g. killzone ai: dynamic procedural combat tactics). However all the papers I have seen so far deal with soldiers. I am trying to find a path for a airplane which has kinodynamic constraints. So a lot of the positions that makes sense for a soldiers tactical point of view doesn't for an airplane. Furthermore waypoints can't be used which these tactical methods depend on. We use RRT trees for exploring the configuration space. Does anybody know if there are any papers which deals with this kind of problem or something related? Or have any suggestioins to where I should start reading? thanks in advance, Erik

I'd guess that this is an area that is not well covered by gamedev

perhaps look into a (real-life) piloting forum? ask if anyone there has experience with dogfighting re-enactments

AFAIK, RRT trees are currently the only really feasible method of exact (well, nearly-exact) kinodynamic path-planning. You may, however, find it useful to add a higher-level planner over that. Dogfighting is based on a number of manoeuvres with certain preconditions and postconditions; your planner can pick from these and carry them out, based on an evaluation of the utilities of each. To execute each move you can use conventional control methods. RRT could be a planner of last resort, useful mostly for evasive actions.

Look at Steven Lavalle's book Planning Algorithms (particularly the chapter on differential constraints) to get a better idea about kinodynamic motion planning. http://planning.cs.uiuc.edu/book.html

Sneftel is close to being correct - there are very few general purpose techniques to do motion planning that will work for *any* model, no matter how complex it or the constraints are other than RRT's. Be aware, the price of using RRT's is that they can be quite slow, especially in complex configuration spaces or situations where there are frequent or expensive collision tests. RRT's by default are meant for static environments in which obstacles don't move - you'll need to do a bit of fiddling to get them working for moving obstacles.

However you can try 'plan and transform' where you plan a free path in the configuration space and then modify it to include the differential constraints. If your model is differentially flat - and for a game you might be able to wrangle this - you can look at some alternative steering approaches. Other alternatives include online optimisation of obstacles constraints and flight dynamics.

Just for interests sake what type of model are you using to simulate your aircraft? How are you representing your obstacles (kill-zones)?

Hey thanks everybody for the input.

Andrew I looked some at LaValle. Actually I think I might have had the book in a motion and manipulation course I took. He is getting a bit to mathematical for met though. It is really time consuming for me to plow through.

Anyway I am not sure how helpful he is. I will look more into it, but it seems he mostly deals with ways of coming around obstacles when one has different constraints on movement. That is not really my problem. Why have a fairly good model working with RRT trees. The steering model is based on a minimum change in angle for pitch and yaw per time unit, for a particular speed. I guess that essentially translates into a minimum turning radius.

But what I want to do is to reason about the environment (terrain). It will not be a like a normal flight sim, because there will be a lot of obstacles. I think the idea is sort like flying between mountain peeks or high rise buildings or something. It is not really meant to be realistic I think.

So what I need to figure out is, what are good positions to attack a player from and what orientation should NPC be in. So I imagine determining things like pinch points to stage a flank attack on player when he/she exits.

Furthermore the NPC needs to fly up to its attack positions following a path that doesn't put it danger (line of fire from other enemies). Now I could calculate a path using a RRT tree by modifying the goodness value for each node based on whether the spot was visible by enemy planes.

However the enemy is not going to be sitting tight, since they are planes. Thus by the time the NPC reaches a potentially dangerous spot, the enemy planes might not even be there anymore.

So I am thinking of partitioning the world up in cells, simulate some flight paths through the world and use this info to annotate the cells with likelihood that enemies will be at cell at a given time.

But I don't know if this is a good idea. Perhaps it is better to estimate an enemy path online and use that to calculate safest path for NPC.

There has been some good work over the past 4 years on risk-based tactical path finding for UAVs. The literature in that field should help you to get a handle on methods for dealing with threats as soft constraints on paths. The typical approach taken is to model threat location as a probability distribution and then use a decision theoretic approach to minimise expected threat over a path between two locations. In your situation, you'd have to include additional terms in your cost functional, to account for your dynamic constraints, but I don't see this as overly problematic. If you have difficulty finding literature on this topic (you shouldn't though, there's plenty online), let me know. I have a bunch of papers on this topic I can forward to you.

Cheers,

Timkin