基于A*搜索算法的改良算法介绍

基于A*搜索算法的改良算法介绍

[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.

阅读更多
规划算法中的图搜索算法简单小结
Paper review Planning and Decision-Making for Autonomous Vehicles
论文研读笔记--"Baidu Apollo EM Motion Planner"

论文研读笔记--"Baidu Apollo EM Motion Planner"

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.

阅读更多
path planning-5次Spline样条曲线光滑算法Demo
论文研读笔记--"Hybrid Trajectory Planning for Autonomous Driving in Highly Constrained Environments"

论文研读笔记--"Hybrid Trajectory Planning for Autonomous Driving in Highly Constrained Environments"

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.
    后面这些名词概念都会得到详细解释.
阅读更多