1
$\begingroup$

I have a 2D plane, with a fixed height and width of 10M. The plane has a robot in the point (1,2.2), and an electric outlet in the point (8.2, 9.1). The plane has a series of obstacles like polygons and implemented with a lot of points in the edges. But not have routes between two points, this is not like a map exactly.

enter image description here

Is there an algorithm to find the shortest path between the Robot and theelectricOutlet?

And if the point has a fixed wingspan? For example, that the space between O and N is smaller than the robot, and then the robot cannot cross?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ This is a typical path-finding problem in robotics. However, I don't see any polygons in your picture or are you saying that the points in the picture represent the vertices of the polygon? $\endgroup$ – nbro♦ Mar 19 '19 at 17:28
  • $\begingroup$ Yes, I can not draw it because the lines extended to infinity $\endgroup$ – Tlaloc-ES Mar 19 '19 at 21:35
  • $\begingroup$ If they extend to infinity, how do you expect to walk around them? $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 19 '19 at 21:47
  • $\begingroup$ in the draw, no the polygon, I used geogebra and I do not know how join two points with a line $\endgroup$ – Tlaloc-ES Mar 19 '19 at 22:09
  • $\begingroup$ @Tlaloc-ES There are ways in GeoGebra to draw polygons. Have a look at the tutorials on the web. Anyway, so, what's your actual question? $\endgroup$ – nbro♦ Mar 20 '19 at 15:24
0
$\begingroup$

The usual way to solve this kind of problem is to construct a configuration space: extruding all the polygonal obstacles by sliding the polygon corresponding to the robot around them (some slides).

The exterior vertices of the configuration space can then be used as input to a path-planning algorithm, such as A*.

Improve this answer
$\endgroup$
  • $\begingroup$ There is no need to construct a configuration space. The C-space in the referenced slides was introduced to explain motion planning for a kinematic chain which isn't necessary in the problem here. A simple pathplanner like RRT will do a great job. I would go even a step further and recommend a brute force search in the map, because the map is small and the number of possible edges is low. $\endgroup$ – Manuel Rodriguez Mar 21 '19 at 18:00
  • $\begingroup$ According to Wikipedia: "An RRT can also be considered as a Monte-Carlo method to bias search into the largest Voronoi regions of a graph in a configuration space." $\endgroup$ – NietzscheanAI Mar 21 '19 at 18:10

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.