3

the standard way is the following: AI: A modern Approach

function UNIFORM-COST-SEARCH

node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
    if frontier is empty then return failure
    node <- POP frontier  /* chooses the lowest-cost node in frontier */
    if GOAL-TEST(node) then return SOLUTION(node)
    add node to explored
    for each action in ACTIONS(node) do
        child <- CHILD-NODE(problem, node, action)
        if child is not in explored or frontier then
            frontier.INSERT(child)
        else if child is in frontier with higher PATH-COST then
            replace that frontier node with child

Here this step is complicated to achieve, a normal priority queue cannot update a certain element's priority efficiently.

        else if child is in frontier with higher PATH-COST then
            replace that frontier node with child

I am thinking to modify the algorithm the following way:

function UNIFORM-COST-SEARCH-Modified

node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
    if frontier is empty then return failure
    node <- POP frontier  /* chooses the lowest-cost node in frontier */
  > if node is in explored then continue
    if GOAL-TEST(node) then return SOLUTION(node)
    add node to explored
    for each action in ACTIONS(node) do
        child <- CHILD-NODE(problem, node, action)
  >     if child is not in explored then
            frontier.INSERT(child)

So I don't care if the frontier contains repeated states. I only expand the first of the repeated states in the frontier. Since the path-cost is consistent, and the frontier is implemented using priority queue, it is not harmful to ignore the other repeated states with higher cost.

Is it reasonable?

Update

Sorry I forgot to mention I am particularly interested in consistent heuristic case.

0

2 Answers 2

3

The idea is correct in principle but there is a bug:

  > if node is in explored then continue

This line might cause failure if the heuristic function is not monotonic (does not contradict admissibility).

A* allows re-exploring nodes if the new cost is better then the previously found. These situations happen in non monotonic heuristic functions.

You should continue only if the new cost is "bigger" then the one attached to the vertex in explored, and not if it only exists there.


EDIT: (based on question on comment and question edit)

For h=0, A* actually decays into Dijkstra's algorithm, and since Dijkstra's algorithm never needs to modify already "explored" node (assuming positive weights, of course) - the algorithm is correct for these cases.

In general, re-visitting already visited nodes does not happen in monotonic heuristic function, so this is not an issue, and the approach is correct for these cases - but beware not to apply it with a non monotinic heuristic function.

5
  • By adding a simple lookup table, you should be able to find in O(1) if a node was already explored, what is the best cost found so far for this node and it's parent. Having this information contained in the Node object can even be easier.
    – Samy Arous
    Oct 2, 2012 at 13:42
  • @lcfseth I agree. The suggestion is simply change explored from a set of vertices to a map:vertex->cost. I believe given the attached algorithm - this modification will be easiest to do.
    – amit
    Oct 2, 2012 at 13:44
  • Sry I assumed it was aimed for consistent/monotonic heuristic, as uniform-cost search use heuristic = 0. so my method should work fine?
    – colinfang
    Oct 2, 2012 at 13:45
  • @colinfang: for h=0, A* actually decays into Dijkstra's algorithm. It should work fine for these cases, since Dijkstra's algorithm does not need to re-visit "explored" nodes. In general, re-visitting already visited nodes does not happen in monotonic heuristic function, so this is not an issue, and the approach is correct for these cases - but beware not to apply it with a non monotinic heuristic function.
    – amit
    Oct 2, 2012 at 13:51
  • Revisiting may also happen if you have a backtracking version of A* (that can compute top-K lists instead of just the optimal result), but in that case you should skip the explored list too.
    – Fred Foo
    Oct 2, 2012 at 15:00
1

Yes, this should work, and I think it's how A* and UCS are explained in AIMA, 2nd ed. You will get repeated states in your priority queue, but only the least-cost version will get returned if you only want to generate one solution/path.

EDIT: misread your program. You should skip the if child is not in explored step when expanding a node's neighbors.

3
  • It works in general - but the suggested modification is not correct. The line if node is in explored then continue will make the algorithm not optimal for non monotonic heuristic function I believe
    – amit
    Oct 2, 2012 at 13:36
  • @amit: you're right, edited. There should only be one check per node to see if it is in explored.
    – Fred Foo
    Oct 2, 2012 at 13:38
  • Sry I assumed it was aimed for consistent/monotonic heuristic, as uniform-cost search use heuristic = 0. so my method should work fine?
    – colinfang
    Oct 2, 2012 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.