I am developing a heuristic solution for blocks world problem.

I tried using number of blocks out of place as my h(n). It seems little ineffective.

Can someone please point out a suitable heuristic for the problem and explain with few examples how it will work.

Blocksworld Problem Example:

Initial(starting State):
Stack 0: D,B
Stack 1: A,E
Stack 2: C
Stack 3: F

Goal State:
Stack 0: A,B,C,D,E,F
  • $\begingroup$ I took the liberty of linking to the wiki for blocks world. Welcome to AI! $\endgroup$ – DukeZhou Sep 25 '17 at 17:58

You may start assigning penalties for undesirable conditions in a state like:

1) Number of blocks outside stack 0.

Supose you penalize with 10 units each block outside stack 0, then the starting state above adds 40 units to the penalty score

2) Number of blocks in the stack 0 in a position different than in the goal state.

Supose you penalize with 50 units each block in stack 0 in the wrong position of the stack 0, then the starting state adds 50 to the penalty score (block D).

And go on you may add as many penalties as you find helpful for solving the problem.

Then for each step you list all possible block moves, for each one of this moves you calculates the total penalty score that this move produces and choose the one move with the minimal score (if ties choose the first one). You keep repeating above until you reach the final state (penalty 0).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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