3

For this 2d grid (black square are not penetrable, white square are):

enter image description here

I want to find path who permit to move an object to a start point (x:18, y:18) to a end point (x:1, y:1), square by square. Imagine this object is an ant or a robot, so:

It can only know the direction of its objective, distance from its objective and if around (1 square distance) square are penetrable or not. Object can keep memory of its path, if it is bypassing because previously blocked, etc ...

  • At (x:18, y:18), ant know X direction is (x:-1, y:-1) vector, distance from X is 18 square, vector (x:-1, y:-1) is penetrable).
  • At (x:17, y:17), ant know X direction is (x:-1, y:-1) vector, distance from X is 17 square, vector (x:-1, y:-1) is penetrable).
  • ...
  • At (x:11, y:11), ant know X direction is (x:-1, y:-1) vector, distance from X is 11 square, vector (x:-1, y:-1) is not penetrable).
  • ?

But it can't know other things. So we can't use here an A* algorithm or Dijkstra's algorithm. Imagine object is a robot in your house. It can test every position like Dijkstra's algorithm but it will take two week to bypass a chair.

Which algorithm can be used to find path from S to X without "walking" on a black square, according to "ant"/"robot" limitations ?

I write some, but with some problems like difficulty to follow "wall" and
go round in circles ...

UPDATE: After Karl Bielefeldt response, i write alogithm available here and procuding: EDIT: I finally not use A* inspiration, but "follow wall inspiration"

AntStar pernal slgorithm

You are free to fork and suggest enhancement !

bux
  • 133
  • 6
  • Do you have any memory of where you've been? – Karl Bielefeldt Jul 08 '15 at 17:38
  • Yes, memory of path, memory of "i'm blocked" etc ... are authorizeds – bux Jul 08 '15 at 17:38
  • 1
    So you're essentially looking for a maze solver? – Ordous Jul 08 '15 at 17:52
  • @Ordous It look like a solution yes. I don't know all maze algo. If one or more of them can resolve it in "robot"/"ant" conditions it will be good ! – bux Jul 08 '15 at 18:03
  • How far can the ant/robot see? *n* distance units? Neighbouring tiles? Only the forward tile? You are looking for some algorithm that takes into account that only limited knowledge about the problem is available. It is clear that a local algorithm will not generally find the globally optimal solution, since it would likely be a “greedy” algorithm and thus be prone to “get stuck” in dead ends. This also reminds me of the “fog of war” in many computer strategy games. – amon Jul 08 '15 at 18:19
  • @bux Those will generally just check all paths one by one, remembering what it already found out. Very slow. For a *good* algo, you'll want directional guidance (A*), smarter backtrack (if another cell is seemingly closer to the objective by 1 move, but it takes 10 moves to get to it, maybe it's not a good idea to go there just yet), checking for shortcuts (In your example - normal backtrack between the 2 "horns" of the trap would take you in an arc, a smart robot would check if there's a shorter path between them) to name just a few ideas. But I'm far removed from research on the topic :( – Ordous Jul 08 '15 at 18:26
  • Is this a homework question... or for an actual robot without knowledge of what is ahead? If the latter, have it follow along the obstruction until its movement towards the target is no longer obstructed. – GrandmasterB Jul 08 '15 at 18:51
  • @amon As say in question: ant/robot can see neighbours tiles. Objective is not to find the optimal solution, but a realistic solution. – bux Jul 08 '15 at 20:32
  • @Ordous Directional guidance is good way i think too. I take note from yours remarks ! – bux Jul 08 '15 at 20:32
  • @GrandmasterB I work on AI ant project: https://github.com/buxx/intelligine Thx for your remarks. – bux Jul 08 '15 at 20:32

2 Answers2

5

If you are allowed to remember past data, A* is indeed your best bet. I used it on Google's Ant AI challenge, which only has a small radius of view.

The main difference with a limited field of view is you do a lot more walking around just to explore, but that's unavoidable. A* will give you a pretty good list of where to explore, without having to visit the entire map.

For fun, I coded a solution for your example. The following is the output:

(18,18)
(17,17)
(16,16)
(15,15)
(14,14)
(13,13)
(12,12)
(11,11)
(11,10)
(10,11)
(9,12)
(8,13)
(8,14)
(8,13)
(9,12)
(10,11)
(11,10)
(12,9)
(13,9)
(13,10)
(13,11)
(14,12)
(15,11)
(15,10)
(15,9)
(15,8)
(14,7)
(13,6)
(12,5)
(11,4)
(10,3)
(9,2)
(8,1)
(7,0)
(6,1)
(5,1)
(4,1)
(3,1)
(2,1)
(1,1)

real    0m0.404s
user    0m0.727s
sys     0m0.040s

It's even more efficient than I anticipated. Only 40 moves, when the ideal with an omnipotent view of the map would be 25. You can see it follows your arrows at first, explores along the wall to the Northwest a little, then turns around and follows the wall until it escapes the indentation, after which it's almost a straight shot. It could maybe be improved even further by tweaking the weights on unseen cells to be proportional to distance from your current position.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
  • Hi, thank's for your answer ! I'm working on Ant AI program ... https://github.com/buxx/intelligine . I will work on your solution and go back here to more information or check your answer ! – bux Jul 08 '15 at 20:37
  • What is the behavior of your algorithm in dead end ? – bux Jul 09 '15 at 13:52
  • Can you be more precise about what you mean by dead end? – Karl Bielefeldt Jul 09 '15 at 14:10
  • I would consider your original example a dead end, just a fairly wide one. As soon as you've explored enough to see all the obstacles in the dead end, the next time you run A* it will plot a course out of it and avoid reentering. – Karl Bielefeldt Jul 09 '15 at 14:17
  • If there's truly no path at all to the goal, A* will exit with an error. – Karl Bielefeldt Jul 09 '15 at 14:20
  • I mean dead end like http://i.imgur.com/VmxDXQP.png . A* remember where it is already "walked". So i imagine it will be without solution at in this dead end no ? – bux Jul 09 '15 at 20:17
  • I design two trap where algo whar i search should success: https://repl.it/wNu 1rst: a pit where do not round in circle, 2nd dead end. – bux Jul 09 '15 at 21:12
  • You have to rerun A* from scratch with your new starting point whenever you learn about new obstacles. That lets you get out of any traps by simply turning around. – Karl Bielefeldt Jul 09 '15 at 21:20
  • Okay, i will try to code that ! I go back soon :) – bux Jul 09 '15 at 21:24
  • My test implementation: https://github.com/buxx/AntStar/tree/master i work but need maybe optimization :p – bux Jul 10 '15 at 15:19
  • I had problems with A* inspiration (circle walk in specific maps). I found solution with "follow wall" inspiration. See my question about it. – bux Jul 18 '15 at 09:04
1

It looks like you are looking for an A* or Dijkstra algorithm.

Depending on the language you are working with, there is likely already libraries built that you can use for these. Here is a some Pseudocode for A* algorithm and an example for Dijkstra's algorithm

EDIT: Although Dijkstra would technically work, it wouldn't nearly as efficient as it should be.

Zachary Dow
  • 165
  • 7
  • Hi, according to my question we can't use an algorithm like A* or Dijkstra. we can only use information around object in movement. – bux Jul 08 '15 at 17:32
  • @bux So it can know where it's objective is (It knows direction and distance, so it can know the location). It can know what it can or can't cross over. Why can't it use one of those algorithms then? – Zachary Dow Jul 08 '15 at 17:36
  • Object can't "know what it can or can't cross over" on all positions. It can know this only for near squares. It add this precision in my question. – bux Jul 08 '15 at 17:38
  • That doesn't matter. Look at an example of Dijkstra's algorithm in action. As long as it has the ability to analyze every move it can take, it shouldn't matter. https://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstras_progress_animation.gif – Zachary Dow Jul 08 '15 at 17:40
  • Imagine object is a robot in your house. It can test every position like Dijkstra's algorithm but it will take two week to bypass your chair ^^ I add this precision to my question. – bux Jul 08 '15 at 17:42
  • 1
    @bux that would make for a hilarious scene in the Termintor 25 movie, with aged characters. – null Jul 08 '15 at 17:47
  • Well, anything you throw at it that would be different than this map could potentially trip up whatever you make short of literally testing all paths. It may be overkill, but this reminds me of neural networks. You can essentially have your robot get smarter over time. Reminds me of MarI/O. https://www.youtube.com/watch?v=qv6UVOQ0F44 The mario kart version seems much like what you're doing: https://www.youtube.com/watch?v=S9Y_I9vY8Qw – Zachary Dow Jul 08 '15 at 17:48