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.

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.

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.

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.

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

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...)