【泡泡航行天下】一种用于最优路径生成的混合整数二次规划方法（ITSC）

泡泡航行天下，带你精读决策规划领域顶级会议文章

标题：Optimal Trajectory Planning for Autonomous Driving Integrating Logical Constraints：A MIQP Perspective

作者：Xiangjun Qian，Florent Altche，Philipp Bender，Christoph Stiller and Arnaud de La Fortelle

来源：ITSC 2016

编译：黄鑫

审核：王隆洪

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

摘要

        大家好，今天为大家带来的文章是——一种用于最优路径生成的混合整数二次规划方法，其中考虑了自动驾驶的逻辑约束，该文章发表于ITSC 2016，.     

        本文研究了连续约束和逻辑约束下的自动驾驶最优路径生成问题。基于连续优化的传统方法将轨迹生成问题构建为非线性规划，其中车体动力学和避障要求分别作为非线性等式约束和不等式约束。通常，采用基于梯度的优化方法寻找最优轨迹。然而，这些方法不适用于逻辑约束，因为有多重机动变量的存在，如交通规则、障碍物约束等。基于此，我们提出了一种新的轨迹规划方法——混合整数二次规划（Mixed-Integer Quadratic Program）。该公式可使用通用的求解器求解，且得到的轨迹可以保证全局最优。我们还将此框架运用在一些仍被认为极具挑战性的自动驾驶场景中，如多机动选择选择避障、迎面超车、最优变道决策等。仿真结果表明了该方法的有效性和实时性。

主要贡献

        1、提出一种自动驾驶轨迹生成的新方法——混合整数二次规划，且该方法可同时处理连续约束和逻辑约束；

        2、在被广泛认为具有挑战性的多种自动驾驶场景下进行仿真实验，实验结果证明了方法的有效性、产生的轨迹为全局最优；

算法流程

MIQP的最优轨迹生成器        

        假设：道路曲率足够小，认为道路为直线，在笛卡尔坐标系 (x, y)中建模，x表示道路纵向，y表示道路横向。

1、车辆动力学及约束（离散化）

        车辆动力学条件：

     动态约束：

2、驾驶逻辑约束       

 

       纵向x设置范围（30m, 50m）的减速带，该范围内车速限制为10m/s。利用大M法求解时，引入二进制变量δ(k)。

3、MIQP公式

        目标函数：

主要结果

       本文采用三阶线性车辆模型生成轨迹，适用于纵向运动大于横向运动的情况，如在高速公路、城市主干道行驶的情况，并分别在减速带、避障、双车道超车、变道等多种场景下进行测试，测试结果表明了该方法的通用性和实时性。

图 1 减速带场景实验结果

图 1 (a) 介绍了减速带模拟场景，图 1 (b) 显示规划轨迹相对于行进距离的纵向速度曲线，可以观察到车辆在[30,50]的间隔内有效地将其速度降低到小于10m / s。

图 2 避障带场景实验结果

图 2 (a) 显示了全局最优轨迹和局部最优轨迹，红色方块表示障碍物，其中的代价函数值分别为，opt 3.16，nopt-1 36.1，nopt-2 37.2，nopt-3 84.67；图 2 (b)、 图 2 (c)分别显示了速度、加速度变化曲线。

图 3 变道场景实验结果

图 3 (a) 介绍了变道模拟场景，图 3 (b) 显示了自身车辆变道轨迹和其他车辆行进轨迹，图 3 (c)、 图 23(d)分别显示了速度、加速度变化曲线；其中，蓝色圆点代表自身车辆，不同颜色的方块代表周围其他车辆，颜色越浅，表明时间相对当前更远。

图 4 双车道超车场景实验结果

图 3 (a) 介绍了双车道超车模拟场景和超车思路，图 3 (b) 显示了自身车辆轨迹，图 3 (c)、 图 23(d)分别显示了速度、加速度变化曲线；其中，蓝色圆点代表自身车辆，不同颜色的方块代表周围其他车辆，颜色越浅，表明时间相对当前更远。

Abstract

    

    This paper considers the problem of optimal trajectory generation for autonomous driving under both continuous and logical constraints. Classical approaches based on continuous optimization formulate the trajectory generation problem as a nonlinear program, in which vehicle dynamics and obstacle avoidance requirements are enforced as nonlinear equality and inequality constraints. In general, gradientbased optimization methods are then used to find the optimal trajectory. However, these methods are ill-suited for logical constraints such as those raised by traffic rules, presence of obstacles and, more generally, to the existence of multiple maneuver variants. We propose a new formulation of the trajectory planning problem as a Mixed-Integer Quadratic Program.This formulation can be solved efficiently using widely available solvers, and the resulting trajectory is guaranteed to be globally optimal. We apply our framework to several scenarios that are still widely considered as challenging for autonomous driving, such as obstacle avoidance with multiple maneuver choices, overtaking with oncoming traffic or optimal lane-change decision making. Simulation results demonstrate the effectiveness of our approach and its real-time applicability.

如果你对本文感兴趣，想要下载完整文章进行阅读，可以关注【泡泡机器人SLAM】公众号。

点击阅读原文，即可获取本文下载链接。

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/bbs/

泡泡机器人SLAM的原创内容均由泡泡机器人的成员花费大量心血制作而成，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！

商业合作及转载请联系liufuqiang_robot@hotmail.com