Deterministic Search Algorithms Part 2

Original article was published by Debby Nirwan on Artificial Intelligence on Medium


Deterministic Search Algorithms Part 2

Solving more realistic planning problems

A more realistic problem, dynamic world

In the previous post we have seen how classical planners solve domain-independent Pacman Planning Problem. Read it here if you haven’t.

Dynamic World

Using classical planners such as in the previous post to solve the problem will work if the world is static and all information are known beforehand. In real life even in games that is often if not always not the case.

The following may happen when our agent is executing the plan:

  • Execution Failures
    This is particularly true if our agent operates in real life using real hardware, the action may fail
  • Unexpected Event
    In our example in Pacman game, this can be meeting ghost while executing the plan
  • Incorrect Information
    The information gathered and perceived by the agent may be wrong at a point of time, it may need to recover after realising it
  • Partial Information
    In Pacman Game, we have full information, but in reality often the agent only has partial information. For example not knowing what is in the room that has not been visited, that’s natural

Let’s see one example below:

We add 2 ghosts to make our Pacman World dynamic. We are using A* planner here to give Pacman the plan to eat all foods in its world.

Because Pacman assumes that the world is static and fully known by it, it fails to execute because it meets the orange ghost in the process.

Repeated Planning and Replanning

To solve this issue we can use approaches that facilitate interaction between planning and acting engines.

There are 3 algorithms that we’ll see:

  1. Lookahead
  2. Lazy Lookahead
  3. Concurrent Lookahead

Lookahead

The lookahead algorithm is simply re-plans after executing one action.

Lookahead(domain, goal):
while observed_world_state != goal:
plan = planner.search(domain, state, goal)
if not plan:
return None
action = plan[0]
perform(action)

In pseudocode above, we can see that this algorithm is only executing the first action, and re-plan with the latest observed world state. This obviously improves our agent, Pacman.

In the video we can see that Pacman is now able to modify the plan to avoid ghosts.

The downside of this approach is that the time it takes to complete the mission is rather long. The replanning is often unnecessary when the dangers (ghosts) are far away from Pacman.

This can be solved by the next algorithm.

Lazy Lookahead

Lazy lookahead executes the plan as far as possible and replans only when current plan will no longer work properly.

Lazy_Lookahead(domain, goal):
while observed_world_state != goal:
plan = planner.search(domain, state, goal)
if not plan:
return None
while plan and current_state != goal and simulate():
action = plan.pop()
perform(action)

In this algorithm Pacman keeps executing the plan until the plan is empty or goal is achieved or the simulate function returns false which means something is wrong in latest observed state, i.e. ghost is just one step away.

This solves the issue in the previous algorithm where the algorithm needs to use a lot of cpu time to re-plan repeatedly.

We can see from the video that the execution time is shorter.

Concurrent Lookahead

The idea of this algorithm is to make the previous algorithm faster by using concurrency. We use multi-threading or in Python multiprocessing to achieve parallelism of planning and acting. However, in reality this is quite difficult to achieve because planning takes longer than acting.

That means the planner does not use the latest observed state of the world if planning is performed while acting. We’ll skip this algorithm.

Other Approaches

There are other approaches such as

  • Limited Horizon Planning
  • Subgoaling

Limited Horizon Planning

With this approach we basically limit our planning to achieve certain threshold, such as plan’s length.

By doing this the agent can change the plan if it found that the plan executed so far isn’t an optimal solution.

However, this approach has the same drawback as previous classical planners. It’s not able to cope with dynamic world with dangers. In other planning problems this approach may work well, but not our Pacman Problem as shown below.

Subgoaling

Subgoaling is breaking down the ultimate goal into sub goals so that we can have shorter plans and cope with changes in the world state. However, this approach is not practical for domain-independent planning. It is difficult to formulate the subgoals.

For domain-specific planning such as path planning, it is more practical where we can use waypoints for example, to achieve the ultimate goal (destination).