A* can't find path in AI game

Question

I want to ask an assignment question. I know some people hesitate to give answers to this kind of question, but believe me, I have spent a lot of time on this assignment and have tried everything I could. So please help if you could.

The question is a rogue-like AI game in a grid format, one of the test cases is a map like the following:

 

g=gold, d=dynamite, ~=water, *=wall, < is our agent, facing left.

The rules are that the agent cannot move into the water nor the wall. It can only move to an empty square or to a d square to pick up dynamite. It can then blast a wall with the dynamite. Once the dynamite is used, it can't be used again. The ultimate goal is to find the gold and pick it up. The agent can only move up and down or left and right. No diagonal moves.

Due to the text formatting, there may appear some extra spaces between the walls in the diagonal direction, but there aren't any.

So far I've used Depth First Search to explore the map. (This example map is quite small, there are some that are big). I've also used A* search to plan for paths, with Manhattan distance as the heuristics.

What's tricky about this map is that, A* search can't find a path to the goal, and the only solution is to first pick up the dynamite near the agent and then blast the second wall to the right of the gold, then go right to pick up the second dynamite, and then go back to blast the last wall to the right of the gold, and then get the gold.

I'm stuck with the following issues:

1. A* search only gives me a path to the goal if it finds one. It doesn't give an "almost-there" path.

2. I can use A* to search for the path either for the gold or the dynamite, but not both at the same time. It seems that, in this case, I need to search the best path for getting the dynamite first and then the gold, in one routine. That sounds too hard...Please tell me if that is the wrong direction.

If anyone has any suggestions or good advice, please enlighten me. I haven't slept for two days...

Thanks for reading.

[EDITED 30/05] Well, I managed to use a trick to solve the above map. Basically, search backward from the gold, and assume if the first level neighboring walls are clear and see if the agent can move there and also can pick up any dynamite from there. if both, then it's a through the path.

But, looking at the following maps, I'm speechless.....can anyone help?

Can anyone shed some light? appreciated...

Answer 1

You could generate a new map after each time a wall is removed and search recursively through all the maps generated...but that would cost a lot of computing. It has a big search space, but it's no bigger than what can actually happen, and that's the point. You don't have to perform a recursive search, A* will simply know which map to use for that part of the search space.

Your A* search space must have to include state changes that involve picking up dynamite and using dynamite on a wall (which changes the connectivity of the map). In other words, you need to search the space of game states generated by all possible agent actions, not just agent movement.

To elaborate a tiny bit: the game state that A* uses should be the current map, the positions of all objects (including the agent), and the agent's dynamite inventory. State changes can have agent movement and (if the agent has dynamite) blowing up any wall segment the agent might be next to. The latter actions will result in successor states having a different map (as well as one less dynamite).

If you wish to know more about Artificial Intelligence then visit this Artificial Intelligence Course.