0
$\begingroup$

I'm working on a project where I want to give instruction to blindfolded participants on how to walk around an obstacle course. I'll map out my room and convert it to a grid map. However, given that I want to minimize the amount of instruction(turns) to give to each person, what algorithm can I use that minimize the amount of waypoints generated, as well as gives some room from obstacles, kind of like in in a potential field algorithm?

My biggest challenge right now is how to convert the path into a series of waypoints that are less granular than the original path. Any ideas?

$\endgroup$
2
  • $\begingroup$ Welcome to Robotics, itisyee. This is an interesting question, but it's probably not necessary to develop an entirely new approach. What has your web searching turned up? What have you tried? Please edit your question to include this. Also take a look at How to Ask and Robotics question checklist for guidelines on how to write a good question. $\endgroup$
    – r-bryan
    Dec 30, 2021 at 22:55
  • $\begingroup$ @r-bryan Thank you for your commend. I looked up basic path finding methods like Dijkstra's, potential field methods, and RRT, and each have characteristics that I want, but I have not found a way to combine them all to do what I want. $\endgroup$ Dec 31, 2021 at 0:55

1 Answer 1

0
$\begingroup$

Honestly, the easiest way to remove waypoints is to simply skip every 1 or 2 or ## waypoints in your Dijkstra or A* (or similarly navigated) map. You do this by looking at the list of nodes to travel to and literally ignoring specifically chosen nodes. Not only do you have to create a path plan for your robot (or people), you need to create a separate algorithm on top of the navigation algorithm that takes care of removing waypoints.

This can be done in a smarter way by looking at the 2-D gradients. In other words, if the grid were an image, you would pass the image through an edge detector filter and try to place straight lines or curves over the edges with fitting algorithms (splines come to mind here).

The problem here is that you need to start from a high precision map, and then remove points to create a low precision map until you start to intersect obstacles or other experiment constraints. The parameters of precision aka. the resolution of the map (like an image) are experiment specific, and are therefore outside the scope of robotics stack exchange. In other words, the "simplification" of the map is an entirely separate problem to path planning.

Note: I am sure there are algorithms that do this automatically, I simply don't know them. Algos like RRT can take advantage of simplification, but those aren't grid based like the question suggests as a requirement, but I may be reading too far into the question.

$\endgroup$
1
  • 1
    $\begingroup$ The CS founder's name is spelled "Dijkstra" (couldn't edit it myself) $\endgroup$
    – r-bryan
    Jan 4 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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