如何通过避障找到从源到目标的路径

Question

实际上我的机器人想要从源移动到目标并避开障碍物。我找出障碍物（矩形形状）和目标（圆形形状）（以像素为单位）。但我不知道如何找到从源到目标的路径...请帮助我。

这是寻找障碍物和目标的代码。

for (int i = 0, n = blobs.Length; i < n; i++)
               {
                   List<IntPoint> edgePoints = blobCounter.GetBlobsEdgePoints(blobs[i]);

                   AForge.Point center;
                   float radius;

                   // is circle ?
                   if (shapeChecker.IsCircle(edgePoints, out center, out radius))
                   {
                       g.DrawEllipse(whitePen, (float)(center.X - radius), (float)(center.Y - radius),
                                    (float)(radius * 2), (float)(radius * 2));
                       target.Add(center.ToString());
                   }
                   else
                   {
                       List<IntPoint> corners;
                       // is triangle or quadrilateral
                       if (shapeChecker.IsConvexPolygon(edgePoints, out corners))
                       {
                           // get sub-type
                           PolygonSubType subType = shapeChecker.CheckPolygonSubType(corners);
                           Pen pen;

                           if (subType == PolygonSubType.Unknown)
                           {
                               pen = (corners.Count == 4) ? redPen : bluePen;
                           }
                           else
                           {
                               pen = (corners.Count == 4) ? greenPen : brownPen;
                           }
                           g.DrawPolygon(pen, ToPointsArray(corners));
                       }
                   }
               }

上面的编码将检测障碍物和目标位置像素值并将其存储在单独的数组中。但是如何根据这些像素值计算路径呢？等待您的建议......

Answer 1

尝试查找 A* 搜索算法。

Answer 2

我没有研究过你的代码，但这是一个经典的路径查找问题。一种建议是将机器人移动的整个区域绘制到网格上。网格可以具有离散单元。然后您可以使用任何图形搜索算法来查找从起始单元格到目标单元格的路径。

您可以使用一些算法，例如 Dijkistra、Best-first 和 A-Star 搜索算法。事实证明，A-Star 高效且易于实施。检查this，包含关于 A-Star 的很好的解释。