Anyone have any info on generating pathing graphs runtime in highly dynamic envirenments? To be very specific, in a Tron type game, any idea what type of representation would lend itself to A*? The problem is that the graph itself is building and removing parts all the time. Paths would be invalidated quickly, with new volumes (or whatever the spatial representation itself ought to be called) created and split frequently. Some sort of hierarchal quadtree type system seems more ideal, but even that seems like it would become unmanagable if the system ran for a few minutes. The number of volumes could get extremely high -- which would be a killer to A*.

You could try D* (Dynamic A*). I believe you can get Stenz''s original D* and Focussed D* papers online at www.citeseer.com.

Path planning and replanning is a very active area of research for mobile agents so spend some time hunting around the robotics literature.

Cheers,

Timkin

quote:
Path planning and replanning is a very active area of research for mobile agents so spend some time hunting around the robotics literature.

thats not necessarily true, actually, im pretty sure that statement is ment for like 20+ yrs ago. modern mobile robots are more heavily into subsumption than complex, literal path planning that be might needed for a virtual robot or game ai.

not to say that there isnt any relevant info available in that feild...

i feel like a dork, but can u describe tron to me?

quote:Original post by EvilCrap

thats not necessarily true, actually, im pretty sure that statement is ment for like 20+ yrs ago. modern mobile robots are more heavily into subsumption than complex, literal path planning that be might needed for a virtual robot or game ai.

Subsumption architectures like that of Brooks have been popular for low-level reactive control of mobile agents, however they are certainly NOT the only thing going on in the robotics community nor the AI community. As for my statement being suitable for 20 years ago, well that''s just plain wrong. My PhD thesis is on automated flight planning and replanning for robotic aircraft so I think I know what I''m talking about when I say it''s a very relevant current topic of research. In fact, subsumption architectures are becoming less popular as researchers realise the limitations of reactive behaviours... like the fact that there are no guarantees about global optimality of control strategies and hence no guarantees about the efficacy of plans.

Timkin

im sorry, but the fast majority of robotics people will tell you that the important ai research isnt bing done in the robotics feild, it is being done in computer science (which, btw, is not robotics). that includes pathing research.

in regards to his question, he said highly dynamic environments. its a fact that planning and replanning without subsumption is not effective in such environments.

THEREFORE he should look into subsumption.

-optimality of control strategies? holy crap, i want to cry.

a system without forms of subsumption is unlike organic systems, and is therefore lacking.

quote:Original post by EvilCrap
im sorry, but the fast majority of robotics people will tell you that the important ai research isnt bing done in the robotics feild, it is being done in computer science (which, btw, is not robotics). that includes pathing research.

It is certainly true that computer science departments do AI research... heck, I am in one myself doing just that... however CS is not the only department type that does AI. Many of the worlds best AI practitioners are NOT computer scientists first and foremost. Additionally, many CS departments have robotics groups... ours for instance! Robotics practitioners are often also computers scientists (and not just engineers).

quote:Original post by EvilCrap
in regards to his question, he said highly dynamic environments. its a fact that planning and replanning without subsumption is not effective in such environments.

That is incorrect. What is your justification for this comment?
Planning and replanning are a major field of endeavour and in fact, very rarely rely on subsumption architectures. Perhaps you should check out the proceedings of conferences such as UAI, IJCAI, the DARPA workshops or even the IEEE Transactions before making such statements.

I can certainly verify that planning and replanning in highly dynamic and complex environements IS possible without a subsumption architecture since I have done it. I have developed an Autonomous Flight Management System for a commercially produced robotic aircraft known as the Aerosonde. This aircraft was originally developed for meteorological research - especially cyclone reconnaissance - and is now being used for surveillance in civilian and military environments. The specific system I developed was for cyclone work, which is most definitely highly dynamic, exceptionally non-monotonic and certainly non-trivial.

If you have evidence about subsumption architectures that invalidates my work - and that of countless others in AI planning - then I would certainly wish to see it. If you cannot substantiate your claims then I suggest you withdraw them.

quote:Original post by EvilCrap
-optimality of control strategies? holy crap, i want to cry.

So you believe that local control strategies CAN offer guarantees about global optimality of plans. Perhaps you should go and read the literature. If you''d like references, I''ll happily provide them.

Timkin

While I agree with your points Alexjc, the question posed by cannelbrae was about the run-time generation of pathing graphs for a highly dynamic environment. Unfortunately the thread has been hijacked.

My original comment still stands: D* is an optimally efficient method for maintaining a partial cost-map of the region of the domain the agent is likely to visit where the transition path costs are expected to change due to a dynamic environment. Other work in this area - at a higher, more abstract level of decision-theoretic planning - has been done by Dean et al (Thomas Dean, Leslie Kaelbling, Jak Kirman and Ann Nicholson).

There are those that reject this classical approach of top-down reasoning about an explicit world model (for the purpose of planning). The work of Rosenschein & Kaelbling on compiled automata was the fore-runner to Brooks'' reactive, behaviour-based robotics. In Brooks'' complete model there exists a heirarchy of behaviours where those higher in the control tree can alter the internal state of lower behaviours. It becomes increasingly clear that to create an adaptive, behaviour-based agent that can do more than avoid a desk in an office, you need to build quite complex, high-level controlling behaviours. To date, only simple mixtures of behaviours have been demonstrated.

This though has nothing to do with pathing graphs. I would like to see the thread head back in that direction please. If anyone wishes to continue the discussion of reactive vs universal planning, let''s start a new thread.

Thanks,

Timkin