A* in Action - Artificial Intelligence for Robotics

A* in Action – Artificial Intelligence for Robotics

这里是一个用在 DARPA 城市挑战赛中的真实算法实现 试验车 Stanford 试图在迷宫中找到一条路 大家可以看到 当汽车运行时 迷宫在不断变化 这显示出汽车正在用传感器探测障碍物 而障碍物在某些时候会被汽车考虑在内 因为只有在障碍物足够近时 汽车才会探测到它们 这是非常值得一提的是 这辆车可以规划出相当复杂的动作来到达目标 在任意时间点上 我们都可以看到 汽车做出了最佳决策找到出路并到达目标 这些橘色的树是 A-star 的搜索树 它们不是严格的网格树 该车的运动与基于网格的机器人有所不同 它可以以不同角度转弯 这里汽车走的每一小步 都是不同的转向角与不同前进动作结合的结果 把这些拿掉 我们就得到这些非常不错的树 它们使用 A-star 来找到通向目标的路径 这个实现运行得非常快 它可以在小于10毫秒时间内 从这个迷宫中的任意一点出发计算出这些树来 据我所知 在参加 DARPA Grand 挑战赛和 DARPA 都市挑战赛的所有团队中 这个算法是最快的 每当机器人取消前一个规划时 这个算法便重新生成一个新的规划 大家可以看到在不同地方它所做的调整 当大家看完这个视频 大家就会明白 A-star 是如何使用一个简单的欧几里得距离作为启发值来找出到达目标的路径的 当大家自己实现这个算法后 Read more…