A* 路径搜索:机器人如何绕过障碍
A* 探索地图时总是先试最有希望的格子,用已走的代价加上对剩余代价的估计。
THE LOOP, STEP BY STEP
The robot repeats this loop many times a second. Tap a step to pause on it.
把地图想象成一张网格。A* 维护一个待尝试格子的列表。对每个格子,它把已走的距离加上对剩余距离的估计,总是先展开总和最小的那个。
这样它朝目标前进,又不忘记到目前为止路线的代价,所以能找到较短的路径,也不会把时间浪费在远离目标的搜索上。
有了它,你可以
机器人能在杂物中找到又短又安全的路线,而且足够快,在东西移动时可以重新规划。
没有它会怎样
试遍所有路线耗时太长,而随机选路则可能绕远路或走进死胡同。
哪里容易出问题
它需要地图和一个好的代价估计。在特别大或不断变化的空间里,需要更快或更轻量的方法。
小测验
A* 用什么来选择下一个格子?