3

The following problem is an exam exercise I found from an Artificial Intelligence course.

enter image description here

"Suggest a heuristic mechanism that allows this problem to be solved, using the Hill-Climbing algorithm. (S=Start point, F=Final point/goal). No diagonal movement is allowed."

Since it's obvious that Manhattan Distance or Euclidean Distance will send the robot at (3,4) and no backtracking is allowed, what is a possible solution (heuristic mechanism) to this problem?

EDIT: To make the problem clearer, I've marked some of the Manhattan distances on the board:

enter image description here

It would be obvious that, using Manhattan distance, the robot's next move would be at (3,4) since it has a heuristic value of 2 - HC will choose that and get stuck forever. The aim is try and never go that path by finding the proper heuristic algorithm.

GengisKhan
  • 65
  • 5
  • 1
    It is not really clear what you are asking. Should you use "hill climbing" to 'optimize' the position, or the path? In the latter case, you could start with a path going straight from start to goal, and "hill-climb" the path to pass through fewer and fewer obstacles, until you find a path that passes through no obstacles at all. – tobias_k Sep 02 '15 at 21:00
  • Thanks for your reply! The "robot", let's call the object starting from S, is going to use the HC algorithm to move. It is not going to be used for optimization - the sole purpose is to force it to move to the F box using a heuristic mechanism. We need to find that mechanism that is not going to get it stuck to the box under S. – GengisKhan Sep 02 '15 at 21:05
  • I think the problem is still underspecified. I understand hill-climbing as local search, which would imply that only local information (like neighboring "states") can be taken into account in the heuristic function. In this case, and using the position as state (and not the path as a whole), I don't think it's possible. But if there are no other restrictions on your heuristic function, you could just say: "Move to the adjacnet square, that has the lowest distance to F using the A* search algorithm" (i.e. using a full A* search as heuristic for greedy search). – tobias_k Sep 02 '15 at 21:15

1 Answers1

4

I thought of the obstructions as being hot, and that heat rises. I make the net cost of a cell the sum of the Manhattan metric distance to F plus a heat-penalty. Thus there is an attractive force drawing the robot towards F as well as a repelling force which forces it away from the obstructions.

There are two types of heat penalties:

1) It is very bad to touch an obstruction. Look at the 2 or 3 cells neighboring cells in the row immediately below a given cell. Add 15 for every obstruction cell which is directly below the given cell and 10 for every diagonal neighbor which is directly below

2) For cells not in direct contact with the instructions -- the heat is more diffuse. I calculate it as 6 times the average number of obstruction blocks below the cell both in its column and in its neighboring columns.

The following shows the result of combining this all, as well as the path taken from S to F:

enter image description here

A crucial point it the way that the averaging causes the robot to turn left rather than right when it hits the top row. The unheated columns towards the left make that the cooler direction. It is interesting to note how all cells (with the possible exception of the two at the upper-right corner) are drawn to F by this heuristic.

John Coleman
  • 51,337
  • 7
  • 54
  • 119
  • Amazing, great solution! – GengisKhan Sep 03 '15 at 09:07
  • This works for that specific map, but it has a lot of assumptions. For example, why count only obstacles that are to the south? This will break if the F field is north of S and there is an obstacle in between. Also, It fails if there is a narrow bottleneck the robot has to pass through to get to the goal. But the text in the assignment specifically asks for a heuristic to solve "this problem", and not "this kind of problem", so thumbs up! Just wanted to point out. – tobias_k Sep 03 '15 at 13:55
  • @tobias_k Good point. I think that without backtracking it is hard to impossible to find a general heuristic that will work on all such problems. You might, for example, need to navigate a maze of obstructions to get to the target cell. – John Coleman Sep 03 '15 at 13:58
  • Another minor correction: The Manhattan distance for the "dead end" should be 2, not 4, but this does not change anything about the result. – tobias_k Sep 03 '15 at 14:08
  • @tobias_k Thanks -- should be fixed now. – John Coleman Sep 03 '15 at 15:05