Is A* returning a constant fscore expected under t

Question

EDIT: I answered my own question. I cant post it as an answer because I have less than 10 rep. I have included it as an edit under the line of ~~~~~~~~~~.

I believe this question does not require a code sample as it is about the algorithm. not a specific implementation.

Suppose you have a grid of nodes each of which are connected to four neighbours with edge weight one (i.e. there is no diagonal movement). The heuristic being used is Manhattan distance. The start is in the upper left corner, and the goal is in the bottom right corner.

Naturally the algorithm will favour expanding nodes to the right or down. The fScore of each such node will be constant because while the heuristic value decreases by one, the distance from start increases by one. This means that there are a very large number of nodes in the open list with the same priority. The order in which they are explored is a result of the tie breaking conditions being used.

Currently I tie break based on the order I check nodes in. That means if all neighbours of a node have equal fScores the priority would be left>down>right>top.

In the example situation this causes my A* to open a very large number of nodes. It first opens each node going down if possible, if that is not possible it goes right. If neither of those options are possible it starts again from the oldest node in the open set (which is usually bad because it is right next to the start.

I think I need a better tie-breaking structure in the case f-scores are equal. Can anyone suggest one to me?

See this example on an 8x8 grid:

0=open node
C=closed node
S=start
G=goal

S    █  
   ██   
      █ 
     █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
O  ██   
      █ 
     █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
O     █ 
     █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
O    █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CO   █ █
█     █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█O    █ 
█       
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█O      
  █ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█CO     
 O█ █  █
█ ███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█O███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CO    █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
CO ██   
CCO   █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCO  █ 
CCO  █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOO █ █
█CO   █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COO  █ 
█CO     
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COCO █ 
█COO    
OC█ █  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COCO █ 
█COCO   
OC█O█  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█COCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCOCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SO   █  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCO  █  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCO █  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCO█  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
COO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCO██   
CCCCO █ 
CCCCO█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCO██   
CCCCO █ 
CCCCC█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCO █ 
█COCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCO █ 
█CCCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCO█ 
█CCCO   
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOO  
OC█C█  █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█O █
█C███  G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█CO█
█C███O G

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█CO█
█C███COG

The fScore of the node being expanded is:14
SCCCC█  
CCC██   
CCCCO █ 
CCCCC█ █
█CCCCC█ 
█CCCOCO 
OC█C█CO█
█C███CCG

The fScore of the node being expanded is:14
SCCCC█  
░CC██   
░░░░O █ 
CCC░C█ █
█CC░░░█ 
█CCCO░O 
OC█C█░O█
█C███░░G

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Better tie breaking condition found!

I am using the std::priority_queue to implement my open node list. It puts the greatest element on top, and requires that you define a comparison function that implements the < operator. I want the least fScore on top so I defined a comparison that is the > operator.

I used to have:

class compareNode {
public:
    bool operator()(map_node* n1, map_node* n2){
        if(n1->fScore  >= n2->fScore) return true; 
        else return false;      
};

Now I made a new comparison function. Based on my intuition that we want to favour nodes that are far away from the start I tie break in favour of nodes that have high gScores. If both the gScore and the fScore of a node are the same I return true (which implicitly favours the node most recently added to the queue)

class compareNode {
public:
    bool operator()(map_node* n1, map_node* n2){
        if(n1->fScore  == n2->fScore){
            if(n1->gScore  == n2->gScore)return true;
            else return (n1->gScore  < n2->gScore);
        }
        else return (n1->fScore  > n2->fScore);
    }
};

See the result of this 8x8 map using the old tie-breaking method, followed by the new tie breaking method.

Old Method:

The fScore of the node being expanded is:14
S░░░░O █
CCO█░O █
█C█O░O█ 
OCO█░O██
OCO█░░O█
OCO██░█ 
OCOOO░O 
█CCC█░░G

shortest path found! This map generated with seed: 13975683

New Method:

The fScore of the node being expanded is:14
SO     █
░░O█   █
█░█   █ 
O░C█  ██
O░C█   █
O░C██O█ 
O░░░░░O 
█CCC█░░G

shortest path found! This map generated with seed: 1397568369

Answer 1

You can use Bounded Relaxation (also known as A*-Epsilon in some books).

A* Epsilon calculates f(v) = g(v) + (1+eps)h(v).

If you use very small epsilon value, you are not loosing the optimality A* offers, while still gaining tie-breaker, according to g(v).
In examples where f(v)=f(u) for all v,u - this variation of A* will result in a behavior resembling DFS - you will favor smaller values of h() - which implies larger values of g(), and in this context this means first exploring branches as far as you can.

Similarly, f you set epsilon as a negative value very close to 0, you will similarly get a tie breaker favoring h(v) - and it will result in behavior similar to BFS.

Answer 2

What you need is a better heuristic, which would incorporate information to "break ties" better. This is, after all, domain-specific information. But keep in mind that, typically, the better the heuristic, the more expensive it is to compute (extreme case: solve the whole problem, so no "search" is needed at all).