Exuse me for my bad english, please. The solution of following problem is very important for me: I have a square map with size N x M (4<N<129, 4<M<129) and it's divided into N X M squares. Each of this squares have value (0, 1, 2, or 3): 0 - this squares are impassable (something like wall). 1, 2, 3 - the cost of passable squares. I also have a goal point on this map with coordinates (x,y) and I must go to it. I don't know where I am on the map, but I can view an eight squares around me. I'm able to move in four directions (up, down, left, right). If you can help me with an algorithm, which finding shortest(costless) path to goal, I'll be much thankful. I don't know my start position and it's the huge problem for me. Thank you! This is one examle of map with size 10 x 12: 1. Map: 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 2 1 1 2 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 2 1 1 2 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 2. Goal coordinates: x=4, y=4 3. My view (I can view an eight squares around me, i.e. I'm in the middle of this showed below): 1 1 1 1 1 1 1 2 1

I need some clarifications first...

Why don't you know where you are on the map? Why do you give yourself such a constrain?

Is this an homework or what?

Eric

This is a challenging puzzle, although it does sound a wee bit like homework.

Unfortunately, if you don't know where you are, you don't know what direction the goal is. I'm not even seeing any way of determining if the goal is within your view given your description.

Without knowing your location relative to the goal, a series of expanding circles is about your best bet, with some pathfinding around blocked locations and a memory of where you have seen.

After all, you may not know where you are going, but it helps to know where you have been.

The puzzle gets simpler if you have access to the map. In that case, it's a pattern match. In your example below, you can be in one of four locations. In that case, you'd move in one around in a circle until your explored area matches with only one possible location on the world map. Then, once you have established your location, then you could A* your way to the goal, given that since you have the map, you know the exact weights of each cell.

Anyway, that's some food for thought.

This is an awful lot like a problem I had for a robot building class: localization on a map when you don't know where you begin. I'll have to make an assumption that the map is provided. Otherwise, this makes it very difficult... The idea that our class had to deal with was sense the local area, then compare that to areas on the map that were similar. Thus, those areas on the map which are closer to that which was sensed have a higher probability of being the correct spot. Of course, there might be more than one. That's where the second part of the alogrithm is: particle filtering. Sample, re-weight the samples based on a transition probability, move, then repeat. Eventually you'll get a probability that will exceed some threshhold or will be higher than all the other cells' probabilities of being the spot you're on. A great reference for this is the Russell/Norvig book Artificial Intelligence: A Modern Approach. After you've localized yourself to the map, you can build up the path using a standard search (e.g. A*).

If you knew where you were starting, you could easily use A* with manhattan distance as your heuristic. My idea would be to try to move to the top left hand corner and then start pathfinding. You could get to the top left hand corner by moving left until you got to a wall. Then move up. You wouldn't be able to guarantee that you weren't stuck in a corner wall in the middle of the map, but in most cases it would work. Otherwise, with no access to the map and no idea where you start, I don't see a feasible solution for localization.

if you don't have a map, or a heuristic which'll tell you where the goal is, your stuffed. (basically, record the map as you see it, and try and find the map, and THEN perform a*. it'll take awhile).

If you do have a map, then you basically check the map that you've seen, against the map of the area.

You end up with a list of possible locations which gets smaller as you see more of the map. Simply try and find a path, which would lower the amount of possible locations.

then you can search to your goal.

Its not too hard.

From,
Nice coder

Actually you're not stuffed if you don't start with a map with which to associate your observations to.

Let's assume there are two possibilities here:

1) You have a map of the domain with movement costs on it, but you don't know your starting state; or,

2) You don't have a map of the domain and therefore you cannot know your state in the domain relative to the entire domain, only relative to observations you have made.

Case 1):

Look up literature on POMDPs (Partially Observable Markov Decision Processes). There is also a wealth of literature in application areas such as robot 'localisation' and 'map-building'. Essentially the problem can be solved as described above. Collect observations and assign probabilities to cells in the map representing the likelihood of being in that cell given the observation history made. Act according to these probabilities to search for the goal if it has not been seen, otherwise move along the lowest cost path to the observed goal.

Case 2):

You must explore the map with lowest cost to find the goal. Here you could solve the problem by considering unexplored areas and the probability that the goal is in each of these areas. One hint (and I'm not going to give too much away here because this does appear to be homework): consider the probability of the goal being at the end of a path of cost 1, 2, ..., N-1, N, N+1,... etc. you want to try and minimise the expected cost to find the goal.

Cheers,

Timkin

Many thanks, everybody! You helped me very much.