0
$\begingroup$

I have read through lectures/ tutorials on A* but they have all been via computer simulations. I have an autonomous wheeled robot that is traversing an unknown map (essentially, it'll be a tabletop with no obstacles but has edges it can fall off of); it has an indoor GPS system, IMU, and cliff sensors. I'm trying input a desired waypoint.

Does the robot assume that everywhere is traversable, break up the map into a grid, calculate the best path, and go for it OR is it supposed to iterate this process? If the latter, how should the robot proceed in iterating? I'm thinking that it would travel in the "best path" until the cliff sensor is triggered and it will have to recalculate a new best path.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ how can you break up the map into a grid, when traversing an unknown map? $\endgroup$
    – jsotola
    Mar 28, 2018 at 21:01
  • $\begingroup$ Can you just assume that everything is traversable until you "see"/ sense an obstacle or an edge? $\endgroup$
    – Erin
    Mar 28, 2018 at 21:27
  • 1
    $\begingroup$ yes you can, but it all depends on the environment that the robot is placed into and the sensors that it has available to it .... you can use your own experiences as an example .... imagine yourself in the middle of a soccer field ... what mode of navigation would you use? .... now imagine that you are in a scrap metal yard, with jagged metal piled up and heavy machinery moving around .... what mode of navigation would you use there? $\endgroup$
    – jsotola
    Mar 28, 2018 at 21:54
  • $\begingroup$ Oh yea, got it. As I mentioned, it's going to be traveling on a flat surface (like a table) with no obstacles, only edges. The only "obstacle" would be the edges of the table where it could fall off (or in your example of the soccer field, I can walk around anywhere as long as I don't go out of bounds). $\endgroup$
    – Erin
    Mar 29, 2018 at 0:43

2 Answers 2

Reset to default
2
$\begingroup$

There is a dynamic version of A* (or of Dijkstra's algorithm) that was developed to address exactly this problem of trying to do planning on a map as you discover it. It is called D* or occasionally Stentz's algorithm after the originator, Tony Stentz. Have a look at this UIUC course page for a good description of the formulation, and the wikipedia entry has more info on variants that have been created over time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you! I will take a look. Didn't realize that Dijkstra's was more of a dynamic map problem. $\endgroup$
    – Erin
    Mar 29, 2018 at 2:08
  • $\begingroup$ What surtur is saying is that Dijkstra/A* - in the context of robotic navigation - applies to static maps, whereas D* is more suited to dynamic maps. Note however that the difference is essentially a matter of computational complexity: D* performs an incremental search instead of 'replanning from scratch' like A*/Dijkstra, so it is faster. But in practice you can still use A* or Dijkstra and periodically replan your path as your discover new parts of the map. It all depends on the computational resources you have available. $\endgroup$
    – al-dev
    Aug 22, 2018 at 16:33
0
$\begingroup$

I don't see any sensors being states that can detect the obstacles.

it has an indoor GPS system, IMU, and cliff sensors.

Indoor GPS and IMU cannot detect the obstacles. The cliff sensor can only sense if the robot is going to fall off the table that if it's near the table edge. None of them can tell if an obstacle is coming into the robot's path. So, first need to have a sensor that can accomplish this. You can look into LIDARs(costly) or cheap ultrasonic sensors depending upon your task.

Now once the surrounding obstacle data is available, an algorithm for path planning comes into play.

Theta * can be used for path planning if the initial map is unknown. Check out this video to see it in action. Hope it helps.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.