运动规划

SUMMARY

学院派的规划流程

  • 前端路径搜索（path finding）

    寻找一个初始的、安全的路径

    低维的、离散的空间

  • 基于搜索（search-based）的路径规划

    1. Dijkstra and A*
    2. Jump Point Search

  • 基于随机采样（sampling-based）的路径规划

    1. 概率路线图（PRM）
    2. Rapidly-exploring Random Tree（RRT） and RRT*

  • 满足动力学要求的路径规划

    1. State Lattice Search
    2. Kinodynamic RRT*（基于随机采样）
    3. Hybrid A*（基于搜索）

  • 后端轨迹生成（trajectory gengeration）

    寻找一个可执行的轨迹

    高维的、连续的空间

  • MINIMUM SNAP轨迹生成

  • 具有硬约束和软约束的轨迹优化

ps:尖端的规划：端到端的导航算法（end to end），基于深度学习的导航算法(learning-based)

自主的移动机器人：感知-规划-控制

image

运动规划（motion planning）的基本要求

  • 安全性
  • 平滑性
  • 动力学可行性

image

MDP（马尔可夫决策过程）&MPC（模型预测控制）

image

image

采用什么样的数据结构，采用什么融合算法

Map

有序地图

  • Occupancy grid map（占据栅格地图）

    grid_map

    feature:

    • Most Dense
    • Structural
    • Direct Index Query（直接的坐标索引）

  • Octo-map（八叉树地图）

    octomap

    image

    feature:

    • Sparse（稀疏的）
    • Structural
    • Indirect Index Query（非直接的坐标索引）

  • Voxel（三维像素） hashing

    image

    值得一提的是，这里存储是将多个voxel信息存在一个block里，再将block存入Hash表中

    VoxelHashing

无序的地图

  • Point cloud map

    pointclouds

    feature:

    • Un-ordered
    • No Index Query

More

  • Free_space Roadmap
  • Voronoi Diagram Map（拓扑地图）