[TOC]

项目实践中使用 Hybrid A*算法(关于图搜索算法的介绍博文)搜索粗轨迹的时候, 由于搜索过程太耗费资源加上很多时候不需要每时每刻进行搜索. 因此需要决定什么时候才会 replan, 提升效率. 本篇文章为调查的总结. 该系列算法都是对 A* 的改进, 都是出自 Likhachebv Maxim 教授或者 Sven Koenig 教授的研究成果.

如果对 A* 搜索改进算法感谢的同学也可以关注这两位大牛的主页, 里面有很多教程以及研究结果, 演示软件等.

Likhachebv Maxim 教授的主页 :http://www.cs.cmu.edu/~maxim/

Sven Koenig 教授的主页: http://idm-lab.org/project-a.html

Likhachebv Maxim 教授研究室还研发出了开源的 SBPL C++ 算法库. 支持在ROS中使用, 不仅包含执行代码,还 包括可视化与 debug 的功能.

SBPL 的代码库, ROS wiki. 支持的搜索算法: ARA*, Anytime D*, ANA*, R* , Multi-Heuristic A*.

回到本文内容, 共介绍了 anytime 类: ARA* (Anytime Repairing A*), Incremental类: LPA* (Lifelong Planning A*),FSA*(Fringe-Saving A*),D* Lite.

[TOC]
本文对规划算法中的图搜索算法做简单小结.内容包括DFS,BFS,GBFS,Dijkstra,A*,D*,Hybrid A*.

[TOC]
对于目前的基于状态机或者部分融入优化cost function里的决策算法,我觉得会很容易走到瓶颈.于是查一下学术前沿的一些决策算法.总结于此文.论文地址

Abstract

三大特点:
(1) The top layer of the system is a multilane strategy that handles lane-change scenarios by comparing lane-level trajectories computed in parallel.
(2) Inside the lane-level trajectory generator, it iteratively solves path and speed optimization based on a Frenet frame.
(3) For path and speed optimization, a combination of dynamic programming and spline-based quadratic programming is proposed to construct a scalable and easy-to-tune framework to handle traffic rules, obstacle decisions and smoothness simultaneously.

本文参考 Apollo 的算法, 实现了对 5 次 Spline 样条曲线光滑算法的 Demo.

Basic info

Author: Yu Zhang
Date: 2018
Juounal: IEEE Acess
Institute: 北理

Abstract

共四方面贡献:

1. trajectory planning framework: 克服 geometry constraints(free space), nonholonomic constraints(vehicle kinematics and dynamics) and dynamics constraints, task constraints (requirements to visit certain intermediate targets)实现 curvature continuous , kinodynamically feasible, smooth and collision-free trajectories in real-time.
2. derivative-free global path modification algorithm to extract high-order state information in free space for state sampling.
3. multi-phase deterministic state space sampling method that is able to approximate complex maneuvers.
4. car footprint approximation strategy and a two-phase collision checking routine.
   后面这些名词概念都会得到详细解释.