Jump to content
  • Advertisement
Sign in to follow this  
TechnoGoth

Parallel obstacle satisfaction planning

This topic is 4870 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I’m not sure if this is correct term or not but, as of yet I haven’t been able to find any reference to this kind of planning so perhaps the members of this forum have some ideas. In connection with some other work I’m doing I’m looking into the problem of solving a problem in which multiple obstacles must be satisfied in parallel. Let me elaborate by providing a scenario in which this problem arises. An agent is must traverse a room that has two doors on opposite walls. The door the agent has to pass through is locked, and in the room are two parallel rows of boxes which run perpendicular to the doors. There are also two security guards each patrols around a different row of boxes. The security guards can see the agent if the agent enters their line of sight. Now as I see it there are 5 types strategies that an agent can use to overcome an obstacle. Avoidance Confrontation External – planning on a action being performed by another agent. Tool – utilizing a device to overcome the obstacle. Environment – utilizing an aspect to overcome the obstacle. In this scenario the guards can be avoided, or confronted, and the door requires a tool to unlock. Further in this case the agent has a lock pick which can be used to unlock the door. The agent’s goal is to get though the locked door which requires it unlock the door. In order to unlock the door it has to avoid or confront the second guard and in order to that it has to avoid or confront the first guard, causing all three objectives to be linked since there is no point of avoiding the first guard if the action causes the agent to be detected by the second. So I’m looking for a way to for the agent to create a plan to solve the problem. At present I’m thinking of two pass method. In which in the first the agent identifies the obstacles and the pre and post conditions that link obstacles together, then performs a standard constrain satisfaction plan to overcome the obstacles consecutively. But I’m concerned that this approach could lead very easily to planning loops. So I’m looking for a better way.

Share this post


Link to post
Share on other sites
Advertisement
I don't see anything parallel about it.

You pretty much have a decision tree to traverse.

Do you confront the first guard?
Do you confront the second guard?
What to do afterwards? etc....

Then you add elements that tie things up. Stuff, like making the decision tree more specific. If you confront the first guard, where do you confront him, such that the second guard doesn't see? Or something similar....

To me, it just looks like a simple decision problem where you want to optimize a certain hidden value, like survival rate, time consumption, final gain, etc.

Share this post


Link to post
Share on other sites
Like most plannning problems, it's a question of sequential decision making, where subsequent decision depend on the results of enacting earlier decisions. If there is uncertainty as to the outcome of any given action, then you could model your problem as a Markov Decision Problem. Policy/Value iteration can be used to find the optimal policy for your agent.

If I've misinterpreted your problem, my apologies for the misleading answer.

Share this post


Link to post
Share on other sites
Maybe I'm just over thinking things. I was considering the fact that to avoid guard one you you also have to avoid guard two at the same time. But your saying this logic is incorret?

It takes Time T to unlock the door, and the agent has to move from Point A to Point B. So the agent needs to find a path P, which consists of move and/or wait actions that will take it from Point A to Point B over Time Interval I. Such that during Time Interval I+T the agent will not be detected by guard 1 or guard 2.

So your saying the I can identify and solve this problem using standard Markov Decision making. Okay I'll have to refresh my memory on Markov since I haven't used it in a while.

Share this post


Link to post
Share on other sites
Quote:
Original post by TechnoGoth
It takes Time T to unlock the door, and the agent has to move from Point A to Point B. So the agent needs to find a path P, which consists of move and/or wait actions that will take it from Point A to Point B over Time Interval I. Such that during Time Interval I+T the agent will not be detected by guard 1 or guard 2.


Maybe I'm missing something, but I don't see how this isn't just a simple planning problem. If, after investigating MDPs, you find that they don't model your problem, please post here and let us know how/why they don't (and whether you have found a reasonable alternative solution method).

Thanks,

Timkin

Share this post


Link to post
Share on other sites
Guest Anonymous Poster


The devil is in the evaluation of the difficulty/cost and risk of doing each specific task in the planner tree (making the planner tree is trival by comparison).
Multiple factors local to each situation point may have to be taken into account.
A metric is needed to sum various difficulty/cost/risk factors into one value
to be able to compare paths to a solution.

There may be uncertainty involved as well that complicates any calculations which opens the possibility of different policies in calculating the best solution (risky vs cautious, optomistic vs pessimistic, etc...). Thus the evaluation results may actually be multi-dimensional (the expected cost (ex - time used moving or unlocking), risk - payoff of saving time over a more costly but certain approach, probability of task failure and need to backtrack or terminate (run into a guard...)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!