导航软件如何规划路径？
路径规划无论在军用还是民用领域都应用广泛，导弹、无人机等飞行器需要进行航路（或航迹）规划，汽车行驶也需要路径规划，它们的底层算法是相通的，只不过汽车路径规划相对而言较简单，只需要在二维平面进行，而且对规划环境以及反应速度等方面的要求没有飞行器那么高。
从本质上来说，底层算法包括两大类：
第一类，是数值优化算法。
它在从起点和终点之间布设一系列路径点，使用坐标值表述路径点位置让汽车沿着这些点行驶。在选择路径点时，就需要定义目标函数，例如，路径长度最短。规划过程中还需考虑到一些约束条件，例如，对咱们日常驾驶的汽车来说，就必须要求路径点都位于已有道路上。然后，借鉴一些现代数值优化算法（比如粒子群算法，它是模拟鸟群、鱼群捕食过程的全局搜索算法），不断地对可能布设路径点的区域进行探索，最终确定使得目标函数最优的路径点。
总体来说，如果路径点规模较大，使用数值优化算法求解路径规划时，问题的维度将急剧增加，导致规划过程所需时间较长，难以满足导航软件的时效性要求。
第二类，启发式算法。
以导航上常用的“A*算法”、“Dijikstra算法”等为代表，它从起始点开始，以一定的步长为单位，进行节点扩展。选取代价值（如路径长度）最小的节点为扩展节点，扩展过程中需要考虑一些约束，例如，转弯半径的限制以及对风险障碍的规避等等，这就使扩展角度不可能总是全方位的。借此一步步扩展，直到当某个扩展节点到达目标终点时，再从终点倒过来回溯到起点，这样把过程中的各个节点串起来，就行为了一条规划的路径。
现今非常具有实用性的是第二类算法――启发式算法。
相关文章
