课程大纲

• 基础知识 (1.5h)

  1. 三种指标（makespan throughout sum-of-cost）

  2. 三个基本问题（complete optimal NP-Hard）

  3. 两种任务模式（oneshot lifelong）

  4. 个体路径规划算法基础（dijstra A* D* RRT DWA）

  1

• 环境设计 (1.5h)

  1. 环境地图基础（网格地图、路网地图、图论基础）

  2. 环境良定义

  3. 环境设计经验（环境饱和性 路网连通性 动态高速路 单向路/十字路口）

  2

• 多机器人路径规划方法 (4h)

  1. 集中式路径规划方法（reduction-based：网络流；A*-based：Hierachical A*, ID, OD,CBS, ICT, SAT）

  2. 分布式路径规划/运动协调方法（局部协调法：协调轨迹/速度/时间窗；优先级法：同步/异步/随机）

  3

• 路径规划方法在实际应用中的扩展 (1h)

  1. 任务随带、任务可交换、考虑运动不确定性下的算法扩展

  2. kiva 系统早期经验

  4

• 考虑路径协调的任务规划算法 (2h)

  1. 任务规划基础、整数规划模型、常用任务分配方法

  2. 一体化任务分配与路径规划算法、速度规划、冲突图规划

  5

• 前沿扩展：动态问题的处理 (2h)

  1. 路网权重动态变化问题（TEN）

  2. 机器人执行不准问题（STN 规划/执行框架）

  3. 滚动规划与分区控制框架

  6

• 实战环节

  实战1： 讲两个案例，1）多机器人任务分配，基于集中式智能方法和分布式拍卖法，不考虑底层路径协调（机器人自己完成）；2）当前的大规模调度算法，不考虑任务分配（贪婪解），路径协调用 Hierachical A* 或分区 CBS。

  实战2： Hierachical A* 或 CBS 或整数规划，写 MATLAB 程序。

  7