21

I'm trying to devise an algorithm for a robot trying to find the flag(positioned at unknown location), which is located in a world containing obstacles. Robot's mission is to capture the flag and bring it to his home base(which represents his starting position). Robot, at each step, sees only a limited neighbourhood (he does not know how the world looks in advance), but he has an unlimited memory to store already visited cells.

I'm looking for any suggestions about how to do this in an efficient manner. Especially the first part; namely getting to the flag.

enter image description here

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
Daar
  • 3,385
  • 4
  • 20
  • 18
  • 2
    and what have you come up with so far? – Mitch Wheat Mar 19 '11 at 11:32
  • 3
    If you were in the position of the robot, what would you do to find the flag efficiently? – Lucas Moeskops Mar 19 '11 at 11:37
  • 3
    @Lucasmus: I think it's hard to find some really smart algo, because the robot doesn't know anything about the world, beyond his limited neighbourhood. @Mitch Wheat: Well, so far I have only come up with a list of desired properties such algorithm would encompass: - minimal repetition of visiting already visited cells - global goal: finding the flag - local goal: avoiding obstacles and infinite loops – Daar Mar 19 '11 at 11:38
  • All of these answers are based on the premise that you have an understanding of how search functions work. If that's unclear, please check the bottom of my [answer](http://stackoverflow.com/questions/5361791/robot-exploration-algorithm/5362304#5362304). I hope that helps to clarify. – T.K. Mar 19 '11 at 13:24
  • Also, many of these answers are very valid for an informed search, whereas this is an uninformed search type question. I tried to address this in the next edit of my answer, [here](http://en.wikipedia.org/wiki/Maze_solving_algorithm#Pledge_algorithm). – T.K. Mar 19 '11 at 13:44

8 Answers8

5

A simple Breadth First Search/Depth First Search will work, albeit slowly. Be sure to prevent the bot from checking paths that have the same square multiple times, as this will cause these algorithms to run much longer in standard cases, and indefinitely in the case of the flag being unable to be reached.

A* is the more elegant approach, especially if you know the location of the flag relative to yourself. Wikipedia, as per usual, does a decent job with explaining it. The classic heuristic to use is the manning distance (number of moves assuming no obstacles) to the destination.

These algorithms are useful for the return trip - not so much the "finding the flag" part.

Edit: These approaches involve creating objects that represents squares on your map, and creating "paths" or series of square to hit (or steps to take). Once you build a framework for representing your square, the problem of what kind of search to use becomes a much less daunting task.

This class will need to be able to get a list of adjacent squares and know if it is traversable.

Considering that you don't have all information, try just treating unexplored tiles as traversable, and recomputing if you find they aren't.

Edit: As for seaching an unknown area for an unknown object...

You can use something like Pledge's algorithm until you've found the boundaries of your space, recording all information as you go. Then go have a look at all unseen squares using your favorite drift/pathfinding algorithm. If, at any point long the way, you see the flag, stop what you're doing and use your favorite pathfinding algorithm to go home.

T.K.
  • 2,229
  • 5
  • 22
  • 26
  • I think the class would look vastly different based on how the engine gives you your information. I had taken a stab at drafting it, but without the interfaces for learning about the environment, it's just comments or pseudo code. – T.K. Mar 19 '11 at 13:40
  • Some cells could be unreachable - is there an elegant way to find out which? – Uros K Mar 21 '11 at 18:42
  • I think the best way would be to look for connected non-traversable cells surrounding it. Perhaps some sort of breadth-first pathfinding that only stepped on non traversable square, with an end condition of finding a path that hit a square twice and contains a square in each movable direction. – T.K. Mar 21 '11 at 18:56
  • What do you think of a space-filling-curve for the viewport and then a mst with prim? – Micromega Mar 21 '11 at 19:33
  • @epitaph For what? to find the distance from a known point to another one? I've never done that before, but I suspect that's be much more computationally intensive than a breadth-first search. Basically what I think that'd be is the equivalent of expanding every single possible path before starting any computations, so it has no hope of ever finishing before that point. Basically, it'd be just like breadth/depth first search always running in worst-case time and space. – T.K. Mar 21 '11 at 20:18
  • @T.K. No to limit the viewport of the robot, because the world is somewhere stored. And if you have that limit view you can run a prim's algorithm or a DFS, or a BFS. – Micromega Mar 22 '11 at 13:53
  • @epitaph I'm sorry, I don't understand what you're saying. Maybe open up another question about it, and explain in more detail? – T.K. Mar 22 '11 at 13:55
3

Part of it will be pathfinding, for example with the A* algorithm.

Part of it will be exploring. Any cell with an unknown neighbour is worth exploring. The best cells to explore are those closest to the robot and with the largest unexplored neighbourhood.

If the robot sees through walls some exploration candidates might be inaccessible and exploration might be required even if the flag is already visible.

It may be worthwhile to reevaluate the current target every time a new cell is revealed. As long as this is only done when new cells are revealed, progress will always be made.

aaz
  • 5,136
  • 22
  • 18
1

With a simple DFS search at least you will find the flag:)

Petar Minchev
  • 46,889
  • 11
  • 103
  • 119
  • ok. say when you gain some information about the location of your base(e.g. it's distance from the lower world-edge), how could you use that to improve such algo? – Daar Mar 19 '11 at 12:06
  • What about a BFS? It's simple too. – Micromega Mar 19 '11 at 13:02
1

Well, there are two parts to this. 1) Searching for the Flag 2) Returning Home

For the searching part, I would circle the home point moving outward every time I made a complete loop. This way, you can search every square and idtentify if it is a clear spot, an obstacle, map boundary or the flag. This way, you can create a map of your environment.

Once the Flag is found, you could either go back the same way, or find a more direct route. If it is more direct route, then you would have to use the map which you have created to find a direct route.

glowworms
  • 410
  • 4
  • 8
0

As many have mentioned, A* is good for global planning if you know where you are and where your goal is. But if you don't have this global knowledge, there is a class of algorithms call "bug" algorithms that you should look into.

As for exploration, if you want to find the flag the fastest, depending on how much of the local neighborhood your bot can see, you should try to not have this neighborhood overlap. For example if your bot can see one cell around it in every direction, you should explore every third column. (columns 1, 4, 7, etc.). But if the bot can only see the cell it is currently occupying, then the most optimal thing you can do is to not go back over what you already visited.

Ben
  • 1,038
  • 1
  • 19
  • 22
0

What you want is to find all minimal-spanning-tree in the viewport of the robot and then let the robot game which mst he wants to travel.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • This will work for informed search, where the robot knows in advance how the grid is. Based on problem description, the Robot isn't fully aware of the environment. – Shamim Hafiz - MSFT Mar 19 '11 at 11:47
  • @Gunner: It's anyway above my capabiities but why not let the robot game about the Euler-Circuit in his next move? – Micromega Mar 19 '11 at 11:53
  • What about a space-filling-curve? That way the robot has an spatial index of +/- 100 or whatever he is seeing then let him find a way by finding every mst and let him choose randomly? – Micromega Mar 19 '11 at 12:28
0

If you met an obstacle, you can go around to determine its precise dimensions, and after measuring it return to the previous course. With no obstacles in the range of sight you can try to just head in the direction of the nearest unchecked area.

It maybe doesn't seem the fastest way but, I think, it is the good point to start.

Rafał Rawicki
  • 22,324
  • 5
  • 59
  • 79
0

I think the approach would be to construct the graph as the robot travels. There will be a function that will return to the robot the particular state of a grid. This is needed since the robot will not know in advance the state of the grid.

You can apply heuristics in the search so the probability of reaching the flag is increased.

Shamim Hafiz - MSFT
  • 21,454
  • 43
  • 116
  • 176
  • What you want is a space-filling curve of the complete graph the you can limit the robot view and let him explore the view with prim's or kruskal algorithm and let him choose one mst out of the many or let him explore the nearest unknown area. – Micromega Mar 19 '11 at 13:00