“优化”是生活中经常使用的词：开车时希望能在安全的前提下以最短时间到达目的地；双11做功课考虑各种优惠活动，希望获得最大优惠；超市进货时需要考虑动销存，最大化提高物品周转效率。 这些问题都是“最优化问题”，也是数学建模中的典型问题，是各大数学建模比赛里的常客。 优化题型有三要素：决策变量、目标函数、约束条件。 （1）决策变量：是决策者可以控制的因素，例如根据不同的实际问题，决策变量可以选为产品的产量、物资的运量及工作的天数等。 （2） 目标函数：是以函数形式来表示决策者追求的目标。例如目标可以是利润最大或成本最小等。 （3） 约束条件：是决策变量需要满足的限定条件。 历年国赛优化问题： 优化问题的出发点是系统思维，其基本思路是在一定的约束条件下，保证各方面资源的合理分配， 最大限度地提升系统某一性能或系统整体性能，最终实现最理想结果。对于这类问题，想要建立并求解数学模型，可以参考以下思路： （1）明确目标，分析问题背景，确定约束条件，搜集全面的客观数据和信息。 （2）建立数学模型，构建变量之间的数学关系，设立目标函数。 （3）分析数学模型，综合选择最适合该模型的优化方法。 （4）求解模型，通常借助计算机和数学分析软件完成。 （5）对最优解进行检验和实施。 PS.北太天元内已有优化工具箱optimization，可以调用工具箱解决优化类问题。 下面给大家分享几种数学建模中常用优化算法： 1、线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。 1.1 用北太天元求解线性规划问题 北太天元内已有优化工具箱optimization，其中的linprog等相关函数可用于求解线性规划问题。 1.2 线性规划特点 优点： （1）作为经营管理决策中的数学手段，在现代决策中的应用非常广泛。 （2）有统一算法，任何线性规划问题都能求解，解决多变量最优决策的方法。 （3）训练速度快。 （4）预测速度快，可以推广到非常大的数据集，对稀疏数据也很有效。 缺点： （1）对于数据的准确性要求高，只能对线性的问题进行规划约束，而且计算量大。 1.3 相关问题 运输问题(产销平衡)、指派问题（匈牙利算法）、对偶理论与灵敏度分析、投资的收益和风险。 2、整数规划 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 2.1 用北太天元求解线性混合整数规划问题 可在北太天元内调用优化工具箱optimization，使用intlinprog等相关函数求解线性混合整数规划问题。 2.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： （1）变量全限制为整数时，称纯（完全）整数规划。 （2）变量部分限制为整数的，称混合整数规划。 2.3 整数规划特点 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： （1）原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 （2）整数规划无可行解。 （3）有可行解（当然就存在最优解），但最优解值变差。 整数规划最优解不能按照实数最优解简单取整而获得。 2.4 求解方法分类 （1）分枝定界法—可求纯或混合整数线性规划。 （2）割平面法—可求纯或混合整数线性规划。 （3）隐枚举法—求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。 （4）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （5）蒙特卡洛法—求解各种类型规划。 3、非线性规划 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 3.1 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。 3.2 相关问题 无约束问题（一维搜索方法、二次插值法、无约束极值问题的解法）、约束极值问题（二次规划、罚函数法）、飞行管理问题 4、动态规划 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decisionprocess）最优化的数学方法。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 5、多目标规划 多目标规划已经应用到科学的许多领域，包括工程、经济和物流，在两个或更多冲突的目标之间存在取舍时，需要采取最优决策。 解决多目标规划问题的方法： （1）将多目标化为单目标 (给多个目标赋予权重) （2）保持多目标不变，根据自己的偏好选择解 实际问题中，目标函数相互冲突是很常见的，例如购买汽车时，要求花费少且舒适度高或者要求性能好油耗低，这种问题并没有绝对最优解（因为并没有确定多个目标的权值），但是我们可以根据自己的需要选择一个相对好的（达到我们想要的最佳平衡）。为了寻求这种“最佳平衡”，可以采用算法帕累托最优（Pareto optimal）。 以上部分内容引用公众号“科研交流”，希望对大家有帮助，觉得有用就点个赞吧。小助手会不定期更新数学建模干货，可以多多关注哟。
数学实验与数学建模：基于Baltamatica作者：华中科技大学 马世拓首先非常感谢北京大学卢朓老师和李若老师等大咖对本项目的支持。这个项目是我春节的时候写的，为了促进新手学习数学建模并推广北太天元软件。书稿是我编写，参考了我大二的时候写的《数据科学基础：from 0 to 1》和正在北大出版社审稿的《MATLAB数学建模》。有些地方可能写的还有点生草，因为的确是对我在前期书稿的一个重排、删改与整合。里面如果有一些有误的地方欢迎与我联系。项目的下载地址链接：github下载链接: github版数学建模教程gitee下载链接: gitee版数学建模教程百度网盘链接：链接：https://pan.baidu.com/s/17Q4_kcgP8Hx7hF6kWaykmA 提取码：g79k为什么要写这本教材我在华中科技大学的时候就很喜欢数学建模竞赛，一直探索数学建模的教与学。我讲过基于Python版本的数学建模，也讲过基于MATLAB版本的数学建模。但是基于北太天元，我们还是第一次尝试。Python和MATLAB这两个系列更多的要求我们“先知其然，后知其所以然”，这也是“学术”和“工程”的辩证统一。北太天元则不同，它是刚起步的，有很多插件还没有弄好，还存在一些底层的问题，所以在使用北太天元做建模的时候要注意从底层原理学习起，宁可学的东西没那么多，但是要理解底层逻辑。这本教材的优点据卢朓老师跟我说，这应该是业内第一本开源的北太天元教程。我的初衷是推广到竞赛中，让学生有胆气冲击北太数模之星的冠名奖。在编写过程中，我不喜欢市面上大多数教材的写法，太死板，也太没人性化。恕我直言，对于那些不讲人话的学术类书稿，你如果是给同行传阅倒也罢了，但是你的受众是学生，我考教师资格证的时候就明确记得有“量力性”这一条要求。不讲人话的书稿我必须得奉上一句“RNM退钱”，所以，我在编写过程中尽可能做到通俗易懂，让读者能够轻易上手接受。此外，书稿大纲是我在华中科大给同学们作数学建模培训磨了几轮才形成的大纲，在此基础上进行了删改，将过于复杂的一些章节去掉了，更容易被同学们接受。作为计科人，我始终记得谭志虎副院长和秦磊华副院长给我们强调的软硬协同观。在本书编写的过程中，虽然更多的是数值计算与模拟方面的东西，但是也同样以自己的理解从软硬协同的角度在看这个软件。本人在计算机领域功力尚浅，是当时专业课学的很拉胯的程度，如果有一些错误之处欢迎批评斧正，读者朋友们见笑。特此声明本书将免费开源不收取任何费用，但是请注意一些版权问题。如果是从我的github或gitee主页下载的书稿，还请star一下可以咩谢谢。最后再次感谢卢朓老师和李若老师等人的支持！~
基于Baltamulink的汽车单自由度振动力学模型的建立由于汽车在行走时，路面不平，汽车行驶中的路面可简化成正弦函数。可把汽车行走的路面看做激励，忽略轮胎的弹性与质量，得到分析车身垂直振动的最简单的单质量系统，适用于低频激励情况。汽车行驶可看作如下模型： 上图为单一自由度系统的简图，设X(t)及Xs(t)分别是质量块及支承的位移，支承的运动规律是：Xs =asinwt由于支承的运动，质量块收到的弹性恢复力为k(X - Xs)，阻尼力为c(Vx-Vxs)根据达朗伯原理可得如下的运动微分方程： 由（1）和（2）得： 在此系统中除了有弹性恢复力及阻尼力作用外，还始终作用于简谐激励力： Px=P0sinwt简谐激励：激励随时间的变化规律可用正弦或余弦函数表示；振动响应亦为时间的正弦和余弦函数（简谐振动）。结合上面的运动微分方程和简谐激励力方程，可得系统的运动微分方程为： 令：物体质：m = 1 kg，弹簧刚度：k = 3 N/m，阻尼：c = 4 N·s/m，作用力P = 2sin(2t + π/3)，研究物体的位移随时间的变化规律。通过北太真元建立系统运动微分方程模型，如下图所示：设置参数：正弦波产生模块：幅值：2；偏置：0；频率(弧度/秒)：2；相位(弧度)：pi/3≈1；一阶积分模块：积分初始值：0.5；增益模块：增益数值：4；常量模块：常量值：3；结束时间：10s；求解器：ode4；步长：0.01s。得到的仿真结果，如下图所示：
问题：二阶电路动态系统中，该系统是由电阻R、电感L和电容C组成的无源网络；ui(t)为输入，i(t)为电流，u0(t)为输出；设R=1Ω，L= 2H，C=2F；系统的初始状态为0，外加的输入为单位阶跃信号。求系统的输出波形。图：二阶电路动态系统首先，在解决该问题时，需要了解基尔霍夫电压定律；它的内容是，在任何一个闭合回路中，各元件上的电压降的代数和等于电动势的代数和，即从一点出发绕回路一周回到该点时，各段电压的代数和恒等于零，即∑U=0。基尔霍夫电压定律表明：沿着闭合回路所有元件两端的电势差（电压）的代数和等于零。或者描述为：沿着闭合回路的所有电动势的代数和等于所有电压降的代数和。以方程表达，对于电路的任意闭合回路有：其中，m 是这闭合回路的元件数目，vk 是元件两端的电压，可以是实数或复数。基尔霍夫电压定律不仅应用于闭合回路，也可以把它推广应用于回路的部分电路。根据上述原理，可写出上面问题的回路方程如下：L di(t)/dt + 1/C∫i(t)dt + Ri(t) = ui(t)消去中间变量i(t)，可以得到描述网络输入输出关系的微分方程为：LC d²u0(t)/dt² + RC du0(t)/dt + u0(t) = ui(t)带入电路参数R=1Ω，L= 2H，C=2F；整理可得：d²u0(t)/dt² + 0.5 du0(t)/dt + 0.25u0(t) = 0.25ui(t)从方面方程可以得到，传递函数分子等式右边系数：[0.25]；分母为左边等式系数：[1 0.5 0.25]根据该系数，在北太真元设计传递函数仿真模型，再加入一个阶跃信号模块，得到仿真模型如下图所示：设置：仿真时长：40s求解器为：定步长；步长：1s；得到仿真结果如下图所示：在MATLAB中创建相同模型，仿真时间、仿真求解器、步长均相同；仿真模型和仿真结果如下图所示： 通过对比发现，北太真元计算结果与MATLAB仿真结果完全一致。
问题：单质量弹簧阻尼机械系统类似于下图，外力f(x)为输入量；质量位移x(t)为输出量；质量m为1kg；刚度为5N/m；阻尼系数f为0.3N·s/m。绘制系统位移输出响应曲线。图1：单质量弹簧阻尼机械系统首先：单质量弹簧阻尼机械系统的震动方程为：m dx²/dt² + c dx/dt + kx = f(x)取状态向量为X(t) = [x(t) dx/dt]’，输出向量为U=[f(x)]，输出向量为Y=[x(t)]，则状态方程为： dX/dt = AX(t) + BUY = CX(t) + DU式中，A = [0 1; -k/m -c/m]; B = [0; 1/m]; C = [1 0]; D = 0;(m = 1; k = 5; c = 0.3)。其次，通过计算得到传递函数的分子分母系数为：[1]； [1 0.3 5];即，传递函数为G(s) = 1/(s^2 + 0.3 s + 5);最后，利用北太真元建立传递函数仿真模型，如下图所示：设置：仿真时长：10s求解器为：定步长 ode4；步长：1s输入常量10仿真结果如下图所示：在MATLAB中创建相同模型，仿真时间、仿真求解器、步长均相同；仿真模型和仿真结果如下图所示：通过对比发现，北太真元计算结果与MATLAB仿真结果完全一致。
1 模型假设1) 忽略转向系的影响，以前、后轮转角作为输入；2) 汽车只进行平行于地面的平面运动，而忽略悬架的作用；3) 汽车前进（纵轴）速度不变，只有沿y轴的侧向速度和绕z轴的横摆运动(ay<0.4g) ；4) 驱动力不大，对侧偏特性无影响；5) 忽略空气阻力；6) 忽略左右轮胎因载荷变化引起轮胎特性的变化；7) 忽略回正力矩的变化。2 模型建立根据模型假设建立如图1所示的二自由度汽车模型。对模型受力分析，存在3个方向的受力平衡，分别为x、y和绕Z的力矩平衡，建立力学方程如下。3 模型仿真在baltamulink中搭建状态空间模型，模型如图所示。（1）在前轮偏转角为1，后轮偏转角为1，车速为40km/h的情况下，输出前后轮的横向位移情况，输出结果如图3。图34 结论通过建立汽车动力学模型，对汽车操纵性进行饿模拟。根据仿真结果可以发现车速和前轮转角都对二自由度汽车的操纵稳定性有很大影响。汽车以较低速度、较小的前轮转角行驶时，是相对安全的。通过分析图3可以看出前、后轮的横向位移都是发散的，这是因为给前轮的一个阶跃响应，一直存在前轮转角，同时系统没有加入闭环控制，属于开环控制，这就导致前后轮的横向位移处于发散状态。附录baltamatica代码如下clc;clear;close all;%% 基本车辆参数v=40/3.6;%输入为km/h，方程单位为m/sm=16000;%车重I=10.85*m;%转动惯量cf=340000;%侧偏刚度cr=cf;lf=2.65;%前轴到重心的距离lr=3.35;%后轴到重心的距离a=pi/180;%% 组装矩阵A=[-(cf+cr)/(m*v) -1-(cf*lf-cr*lr)/(m*v^2) 0 0 -(cf*lf-cr*lr)/I -(cf*lf^2+cr*lr^2)/(I*v) 0 0 v lf 0 0 v -lr 0 0];B=[cf/(m*v) cr/(m*v) cf*lf/I cr*lr/I 0 0 0 0];C=[0 0 1 0 0 0 0 1];D=zeros(2,2);
点击链接查看：英才计划与中学生培养（一）：卡脖子形势下，人才培养方向何在？本文为北京大学重庆大数据研究院基础软件科学研究中心执行主任、北太振寰创始人卢朓副教授在中国科协组织的中学生创新人才培养论坛上的分享。前文观点 计算是求解数学模型的手段。可是对于中学生来说，很多算法的实现并非易事，因此可选择的可以求解的数学模型就很少了。例如，求函数的最大值的问题，往往只能对二次函数，三角函数来求解，稍微复杂的函数就不会了。使用数值计算通用软件，消除中学生求解难的疑虑 其实，很多数学模型对中学生来说还是比较容易掌握的。为了让学生建模的时候可以选择更多的模型，我建议学生使用数值计算通用软件来消除求解难的顾虑。 借助数值计算通用软件，更有利于培养同学们的数学建模能力，我举几个例子： 第一个例子是线性规划、二次规划和整数规划之类的模型。实际上，中学生已经接触过这样的问题了，但是往往局限在很小的数值范畴内。这种模型的威力并未得到充分展现。 中学生如果使用数值计算通用软件来求解此类问题，那么就可以把更多精力放在体会这种数学模型的特点上。 我在B站上给出了一个视频，展示了如何使用数值计算通用软件求解整数规划问题，我相信感兴趣的中学生可以很快学会使用计算机求解整数规划问题的方式。 第二个例子与使用常微分方程的初值问题建模有关，这个可以和物理学科结合起来。我们可以通过测量物体在不同时刻的位移，把数据画出来，借助于常微分方程给出物理运动规律，这样就是在重走牛顿当年的发现之路。至于常微分方程初值问题的求解则可以借助数值计算通用软件来完成。 第三个例子是关于机器学习和人工智能的算法。 我在B站上给出了如何使用数值计算通用软件读取Excel数据，然后如何使用朴素贝叶斯来判断西瓜好坏的例子，也可以供中学生学习。 总之，我建议中学生借助数值计算通用软件来了解读取数据、数学建模、数值计算以及计算结果的可视化等环节，然后选取自己感兴趣的部分多下功夫，其它环节则可以通过数值计算通用软件具有的内置函数以及插件来完成。 参加“英才计划”的学生不一定都要找现实中的问题来做数学建模，还可以通过阅读文献来学习。如果对数学或者其他学科的某些定理和知识点感兴趣，可以通过数值计算通用软件来验证，加深对这些定理的理解。 这样的计算不能代替证明，但是帮助大家体会这个知识点的含义。 通过“英才计划”，我希望学生在多个方面有所收获，如： 1.提升搜集、理解、组织数据的技能，数学建模能力，团队协作能力以及论文写作能力； 2.培养定量研究发展变化规律的习惯，培养好奇心、想象力、创造力和表达力； 3.了解计算机算法和原理、数值计算通用软件的基本用法，对数学知识的用途有更深的认识等。从数值计算通用软件的推荐谈开去：“被禁”以后，我们该做些什么？ 科学计算已经成为与理论和实验并列的科学研究的基本手段。科学计算软件可以分成两种类型：专用型和通用型。 通用型科学计算软件是开发工业软件的重要基础性工具，长期以来，这一部分的市场由国外公司垄断。通用型数值计算软件就好像连接各个工厂的高速公路一样，是数值计算软件中的基础设施。有了高速公路的连接，工厂的原材料才能运进来，生产的产品才能更方便地送到用户手里。 在向参加“英才计划”的学生推荐数值计算通用软件时，我最初考虑的是MATLAB。但由于这是一款商业软件，我担心购买软件会给学生带来额外的经济负担，所以并未选择。 2020年，美国商务部宣布新增33 家中国公司及机构列入 “实体清单”，中国大陆共有 13 所高校被列入该清单，分别为哈尔滨工业大学、哈尔滨工程大学、中国人民大学、北京航空航天大学、西安交通大学、西北工业大学、四川大学、电子科技大学、湖南大学、国防科技大学、同济大学、南昌大学、广东工业大学。MATLAB 所属公司 MathWorks 中止了对以上高校的正版授权。 这让我为当初自己的选择感到庆幸，也让很多人意识到通用型数值计算软件是一个“卡脖子”技术，没有这个技术，我们自己开发的专用软件或者算法就无法得到广泛的应用。但当时我仍想着：好在，我们还有Python可以使用。 可在俄罗斯-乌克兰战争爆发后，据相关报道显示“目前已经有多达30个开源项目加入了对俄罗斯的抵制，其中甚至包括亚马逊（AWS Terraform modules）和Oracle等科技巨头的项目，也不乏MongoDB、pnpm、es5-ext、Drupal、Redis Desktop Manager等流行项目”。这让我进一步认识到：这类开源软件的主导权如果是掌握在别人的手里，仍然蕴藏着危险。 事实上，中国的基础数学和理论数学研究在国际上还是处于领先地位。在涉及具体的算法或专用型数值计算软件领域，我们中国的科学家也取得了很好的成绩，在有关算法的顶级杂志上，中国人发表论文的数量和质量都位于前列，有很多算法被国外的通用型数值计算软件集成，得到了广泛的应用。 但是我们缺乏像MATLAB这样的数值计算通用软件。这是为什么呢？ 因为，通用型的数值计算软件的开发需要耗费大量的时间，需要投入大量的人力物力，无法在短期内做出高精尖的成果。研发过程中需要有关键的技术基础，要掌握核心关键的规律、知识和方法，这些都只能通过“学中干”和“干中学”相结合才能获得。 工业软件可以说是现代产业体系之魂。目前，欧美的工业软件几乎已经渗透了所有工业领域的核心环节。发展具有自主知识产权的工业软件刻不容缓，对掌握我国产业发展的主导权，增强工业体系的韧性和抗打击性都非常重要。 而通用型数值计算软件的研发意义尤为重大：它不仅自己就是一个工业软件，还能够成为其他工业软件的底座，防止国产工业软件被釜底抽薪；同时，数值计算通用软件也是一个非常好的创新平台；正如前文所述，此类软件对于人才培养也至关重要。 通用型数值计算软件的成功研发，将是对人类文明的贡献，也是国家软实力的标志之一。因此，虽然困难重重，我和其他志同道合的伙伴们还是决心开发具有自主知识产权的通用型数值计算软件，破解“卡脖子”问题。 （未完待续）作者简介
17.1 原理 完整思想请看我前面写的路径规划（十三）基于搜索的路径规划算法-前言,，和其他的基于搜索的路径规划算法的区别仅在于启发式函数的不同. 双向A*则稍微复杂些，但可以简单理解为起始节点和终点同时将对方视为目标节点，并按照A*的启发式函数，相向生长，当两者相遇时，则停止迭代，并分别往回追溯自己的父节点即可得到路径。17.2 程序示例
16.1 原理 完整思想请看我前面写的路径规划（十三）基于搜索的路径规划算法-前言，，和其他的基于搜索的路径规划算法的区别仅在于启发式函数的不同 A*则是结合了Best-first Searching和Dijkstra，它将当前节点到初始节点和到目标节点的距离之和作为启发式函数。16.2 程序示例16.3 参考A Formal Basis for the heuristic Determination of Minimum Cost Paths
15.1 原理完整思想请看我前面写的路径规划（十三）基于搜索的路径规划算法-前言，和其他的基于搜索的路径规划算法的区别仅在于启发式函数的不同Dijkstra则和Best-first-searching相反，它不是将到目标节点的距离作为启发式函数，而是将到起始节点的距离作为启发式函数。15.2 程序示例
14.1 原理这里的Best-first-searching和数据结构里学的图搜索算法BFS（广度优先搜索）不是一个东西。完整思想请看我前面写的路径规划（十三）基于搜索的路径规划算法-前言下面说说Best-first-searching的核心思想：Best-first Searching的启发式函数f(x)=dist(x,x_goal)，即Best-first Searching每一步都在预选集合中寻找距离目标节点最近的的那个节点。这里的dist(x,y)，如果节点x,y无法通过碰撞检测，则为inf，如果能通过碰撞检测，可以直接用欧几里得距离代替。14.2 程序示例14.3 参考https://blog.csdn.net/potato_uncle/article/details/109124362?ops_request_misc=&request_id=&biz_id=102&utm_term=best%20first%20search&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-109124362.nonecase&spm=1018.2226.3001.4187
基于搜索的路径规划算法基本都是一个套路，它们都是根据启发函数重备用节点的集合中来寻找下一个节点，不同的启发函数也就有不同的搜索类算法。搜索类算法是离散化的算法，体现在整个图的区域是由有限个小方块区域组成的。我们暂且把这些小方块区域称为“节点”。因此，整个区域被有限个节点填充，且每个节点的邻居节点为有限个。设置两个集合OPEN,CLOSE，OPEN初始状态设为{x_init}，CLOSE 初始状态设为空集。依据不同的启发式函数，从open集中选择一个点加入到close集中，然后拓展open集，如上图，右下角的某个点被某种启发式函数选中，加入到close集中，并相继拓展open集下面介绍下搜索类算法的前进过程：当上述伪码退出循环后，沿着x_goal的父节点往前回溯极为路径各搜索类算法的区别在于第三行启发函数的类型的不同，导致连接的节点不同。
几种RRT对比如下：几种RRT对比视图mp4 RRT及其变种都是依托于采样+在树结构上加减枝的形式进行路径规划的，具有全局收敛特性，但是效率稳定性不高。不过可以针对性地对其主要函数进行优化进行效率的改进：优化采样，优化树结构等。一种加速RRT的思路就是，从起始点和目标节点同时生长RRT树，这就是connected_RRT。此外，针对变化的环境，还有extend_RRT和Dynamic_RRT。 RRT*是一种趋近于最优路径的方案，它通过重布线来实现这一目的，它在理论上能达到最优解，但它全局随机撒点的特性导致它在远离目标路径的地方做了过多的生长。 为了集中优化资源，RRT*-smart应运而生，它比较在乎路径和障碍物的拐点的附近的优化，它通过路径优化步骤判断出路径和障碍物的拐点，并在拐点的邻域内投入更多的资源（即撒更多的点），以实现集中优化资源。 但RRT*-smart依然浪费了太多的随机点在远离目标路径的区域，那什么才叫不远离目标路径的区域呢？informed RRT*则解决了这一问题，它利用初始路径的长度，起始点和目标点，画出了一个椭圆，informed RRT*认为，这个椭圆区域就是不远离目标路径的区域，生成这个椭圆后，后续的随机撒点只洒在这个椭圆区域内，当更优的路径被发现，则根据这个新路径的长度，缩小椭圆，进一步在有效区域集中撒点资源，以实现加速。 然而，RRT*类的算法是总会面临一个问题，那就是重布线，这个令RRT*能够逼近最优解的创新恰恰成为了它慢的原因。 于是，另一种思路被提出，那就是提前给定随机点，然后通过启发式函数来连接这些点以生长路径，这就是FMT*，FMT*专门针对解决高维构型空间中的复杂运动规划问题，在预先确定的采样点数量上执行前向动态规划递归，并相应地通过在代价到达空间中稳步向外移动生成路径树。FMT*能很快的找到一条路径，但是当我们想对这条路径进行优化时，只有通过加密随机采样点的方式，然而，FMT*是一种单批算法，面对新的采样点分布时，它只能重新开始计算。 为了融合informed RRT*在有效区域集中随机点的特点和FMT*快速生长的特点，就诞生了BIT*。它能够在椭圆区域内分批撒点，实现快速生长的同时，还能自我优化。参考https://www.youtube.com/watch?v=TQIoCC48gp4
11.1 原理 简单来说，BIT*是结合了Informed RRT*和FMT*的优点的一种算法。回顾一下，Informed RRT*是对RRT*的一种优化，在RRT*生成一个初始路径后，则以初始路径的长度，起始点和目标点为焦点，画一个椭圆，Informed RRT*在后续随机采点时，只取落在这个椭圆内的点，一次采一个点，重复lm次。FMT*则与RRT那一套不同，它不是边采点，边生长树，而是一次性提前在整个区域（不包含障碍物区域）内采lm个点，只重复一次。 下面我们来说说，Informed RRT*和优缺点FMT*，然后就知道为什么要引出BIT*了。 先说FMT*，FMT*的优点是从起始位置开始构建，没有重布线过程，因此节约时间，适用于复杂的障碍物环境。但是FMT*的缺点是，它只有1批，FMT*路径的精度完全取决于当前批撒点的密度，当你想要提升精度时，只能重新开始一批，重新更密集的撒点，然后重新开始规划。 再说Informed RRT*，Informed RRT*的优点恰好弥补了FMT*的缺点，想要提升精度，只需撒更多的点就好了，而Informed RRT*的撒点过程时一直在进行的，它一批只撒一个点，重复很多批，开始新的批的时候之前的信息不会被抛弃，只要Informed RRT*一直撒点，就可以达到任意精度。但是Informed RRT*的缺点也显而易见，它需要重布线，计算效率低。 所以自然就想到，能不能利用FMT*的优点，提前撒好点，不用重布线，提升计算效率，又能多批进行，以不断提升精度？当然能，这就是BIT*算法 BIT*的过程总结为下图：11.2 伪码11.3 参考1、Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search2、Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs
10.1 原理 在RRT中，当初始路径已经生成之后，如果重点在初始路径周围进行采样的话，可以明显提高路径优化效率。Informed RRT就是进一步优化了采样函数，采样的方式是以起点和终点为焦点构建椭圆形采样区域。 回顾一下RRT*-smart，因为在某区域撒点越多，该区域的优化效果越好，而单纯的RRT*是在全域内随机撒点，优化效果没有得以集中，RRT*-smart认为经过路径优化后的路径的拐点在障碍物的附近，它认为这个拐点的附近需要着重优化，所以RRT*-smart在进一步撒点的过程中，将一些随机点偏袒的撒在这个拐点的附近邻域。 这里的informed RRT*也是这样认为，它认为单纯的RRT*在整个区域内随机撒点，优化效果太过分散，如果我能知道我最终优化的路径在哪一块区域，那我就只在这一区域内撒点不就好了吗？informed RRT*就是这样做的。注意： informed RRT*是在RRT*算法给出一条初始路径后，对这个初始路径继续优化的步骤才起作用的，它对于这个初始路径的生成没有帮助。10.2 思路 根据高中数学知识可以知道，在椭圆上的点到椭圆两焦点的距离之和相同，椭圆外的点的距离到两焦点的距离之和大于椭圆上的点到两焦点的距离之和，椭圆内的点反之。 回顾一下RRT*的搜索图，根据上面这个知识点可以发现，其实RRT在已经得到一条可行路径之后，可以将采样空间收缩到一个椭圆形区域中，区域之外的点对于缩短规划出的路径长度并没有实际价值。 informed RRT就是的主要思想就是上面这种思想，在获取可行路径之后，将采样空间限制在一个椭圆形区域中，并且随着路径长度的不断缩短，逐渐缩小该椭圆形区域。这个思想其实在以前就有，但是提出informed RRT的论文中提出了对这个椭圆形区域直接采样的方法。 可能有人会直接想，这里只不过是缩小了采样空间，并不会明显改进算法。但是实际上，当拓展到高维空间时，效率的提升是巨大的。那么，如何表达这个椭圆呢？下面介绍椭圆采样区域的表达方式方法1：先在标准椭圆的方程中采样，再将采样点旋转平移到实际采样区域，需要两个矩阵：平移向量、旋转矩阵。这两个参数只需要在初始化时计算即可转换后的坐标为：方法2：利用超椭圆体然后在二维平面映射这里放一段.m文件取椭圆随机点的代码（思路如方法2）：除了采样过程外，Informed RRT*的流程和RRT*是一样的。10.3 伪码伪代码中是在RRT的伪代码基础上改的，标红的地方是informed RRT 更改的地方。可以看出，其实主体框架上面并没有太多更改，实际上也是，主要的更改都在第七行，也就是采样这一步。这是采样这一步的伪代码。informed RRT将目前已经搜索到的最短路径作为cbest，起点和终点之间的距离作为cmin，以此构建椭圆。当还没有规划结果时，cbest为inf，也就是和经典RRT没有区别。10.4 程序示例程序在寻找初始路径的过程和普通RRT*一样，在全局域中随机撒点，迭代到1282次时首次找到初始路径，然后我们以起始点和目标点为焦点，初始路径的长度为点到两焦点的距离之和，画出一个椭圆：我们随后的随机点的选取范围不再是全局域了，新采的样本点被限制在这个椭圆中，下图中的圆圈代表迭代1283-2509次的随机点的分布，可见，新的随机点全部被限制在椭圆中：当迭代到2510次时，新的总长度更短的路径被找到，，随后，我们以起始点和目标点为焦点，以这个新的路径的长度为到两焦点的距离，画出一个比之前更小的椭圆：同样的，迭代次数为2510-2865次的循环中的新的随机点被限制在这个新的更小的椭圆中，使随机点资源进一步集中：当迭代到2866次时，找到一个路径更短的路径：10.5 参考Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic
9.1 原理 FMT*算法专门针对解决高维构型空间中的复杂运动规划问题，它是为高密度障碍物的环境构建的算法。该算法被证明是渐近最优的，并且比同类型算法（RRT*）更快收敛到最优解。FMT*算法在预先确定的概率绘制的样本数量上执行“惰性”动态规划递归，以生长路径树，该路径树在成本到达空间中稳定地向外移动。 FMT*的最终产物是一棵树，它在连续空间中获取一批样本，然后它能在图中使用惰性的动态编程搜索该样本集合，并以此找到路径，这也是一个渐进最优的解决方案，FMT*相比于RRT*的加速效果优势在高维和碰撞检查很昂贵的情况下尤其突出。很棒的一点是，FMT*是从起始位置开始构建，而不是像RRT*是在空间的任意位置采点，因为这可能会得到非常远的点或非常近的点，这有什么好处呢？这意味着你不必在树中回溯以进行重布线，因为这在计算上效率低下。FMT*比RRT*更好，因为它创建的连接接近最佳，没有重布线。 FMT*算法在预先确定的采样点数量上执行前向动态规划递归，并相应地通过在代价到达空间中稳步向外移动生成路径树。FMT*执行动态规划递归，其特点有三个关键特征:·它是为磁盘连接图量身定制的，其中两个样本的距离低于给定的界限（称为连接半径）则这两个样本被认为是邻居，因此是可连接的。·它同时执行图构造和图搜索。·为了评估动态规划递归中的即时成本，算法“懒惰地”忽略了障碍物的存在，每当与新样本的局部最优(假设没有障碍物)连接与障碍物相交时，该样本就会简单地跳过并留待以后，而不是在邻域中寻找其他连接。注意：FMT*的样本点是提前生成好的，然后把这些点固定，再利用这些固定好的点来生成行进树，注意区别于RRT*那一套，RRT*是生成随机点的同时，生成行进树。9.2 算法思路上图（a）是RRT*添加新节点的某一步，上图（b）（c）是FMT*添加新节点的某一步。 先看RRT*，节点9是新考虑的节点，它在第一次重布线时，需要从它的所有邻居节点中找出一个父节点，使得节点9到达起始节点的cost最小，因此节点9需要计算它到4、5、6、8号节点的距离并同时进行碰撞检测，因此，第一次重布线过程就要求待加入的节点对它的所有邻居节点进行一次碰撞检测，第二次重布线过程也需要计算距离和碰撞检测，但这在第一次重布线过程中做过了，可以记录先来直接利用，因此第二次重布线过程碰撞检测这一步可以不用重复进行，因此，总的来说，RRT*每新加入一个节点，该节点需要对它的所有邻居节点进行一次碰撞检测。 再看FMT*，上图（b）（c）中的x就是新考虑的节点，在图（b）中，x需计算它到集合V_open中所有的邻居节点的cost，但不需要进行碰撞检测，从中选择一个能使它到达初始节点总cost最小的节点作为它的父节点，然后，对它和这个父节点的连线进行碰撞检测，如果能通过碰撞检测，则加入x，若不能，则下一个x，因此，总的来说，FMT*每新加入一个节点，永远只需要进行一次碰撞检测。FMT*比RRT*每新加入一个节点需要进行的碰撞检测次数少得多，而且FMT*也是渐进最优的，这就是FMT*相比于RRT*的优势所在。9.3 伪码9.4 程序示例下图中的 圆圈代表提前采好的随机点9.5 参考Fast Marching Tree: a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions∗
8.1 原理 最初，RRT*-Smart 像 RRT* 一样随机搜索状态空间。类似地，找到第一条路径就像 RRT* 会尝试通过配置空间中的随机采样来找到路径一样。一旦找到第一条路径，它就会通过互连直接可见的节点来优化它。此优化路径产生用于智能采样的偏置点。在这些偏置点，采样以规则的间隔进行 随着算法的进展和路径的不断优化，此过程将继续进行。每当找到更短的路径时，偏差就会转向新路径。 RRT*是一边生长一边优化的，RRT*的重心在于找到最优路径。RRT*树生长到能连接起点和终点后，这就已经有一条初始路径了。 这颗RRT*树可以继续生长，越生长可以得到的路径相比初始路径会越优。然而，这个继续生长的过程对于RRT*而言效率非常低，由此衍生出RRT*-smart算法，专门解决这一问题。 注意到，RRT*-smart是在RRT*算法已生成初始路径后，在此基础上，想对初始路径继续优化的步骤才起作用，所以RRT*-smart对于生成初始路径并没有加速帮助。 RRT*-smart的优势在于：它专注于提升路径接近障碍物拐点处的优化速度。RRT*-smart算法的思路是这样的：在原始RRT*算法的基础上加了两步：①路径优化路径优化的本质是利用三角形两边之和大于第三边 假设RRT*生成的初始路径长这样 具体操作如下： 一旦RRT*给出了一条初始路径，将初始路径中彼此可见的节点直接相连。迭代过程从xgoal开始，向xinit检查与每个节点的连续父节点的直接连接，直到无冲突条件失败。下图给出一个示例。 信标（Z_beacons）：经过路径优化后的路径中除了起点和终点之外的节点，标记为信标（Z_beacons），如上图中的绿点。②智能采样在RRT*算法中，在生成初始路径后，在此RRT*树的基础上继续采点，采点越多，路径优化效果越好，但此采点，是完全随机的采点，因此效率低下，RRT*-smart则不是完全随机的采点。在RRT*-smart算法中，利用了这样一种思想：智能采样背后的想法是通过生成尽可能靠近障碍物顶点的节点来接近最优性。在基于采样的RRT*-smart中，路径仅沿着靠近障碍物拐点的外围进行优化，解决的办法就是：在障碍物拐点的外围多多采点。如下图所示： 问：那么RRT*-smart如何实现在障碍物拐点的外围多多采点呢？答：利用①路径优化过程中给出的信标（Z_beacons）。一旦找到初始路径，智能采样就会开始，在以Z beacons为中心的半径为R beacons的球中直接生成一定数量的样本。采样偏向于这些信标，因为它们提供了有关障碍物顶点（或圆形障碍物的外围）位置的有用线索。因此，这些信标需要被最大节点包围，以优化这些转弯处的路径。与 RRT* 相比，这一特征迫使所提出的算法以更少的迭代次数达到最优解。注意：信标（Z_beacons）是需要随着优化路径的更新而更新的。即当z_goal.cost变小时，说明路径得到了优化，那么就要启用之前①路径优化算法来重新确定新的z_beacons。 8.2 伪码 8.3 程序示例下图中的线段代表由RRT*生成的初始RRT树，圆圈代表在初始RRT树基础上，继续采点的分布，可见在几个“拐点处”的圆形领域内我们有额外的采点以加强在这部分的采点 路径优化后确定出拐点 经过路径优化后的路径： 8.4 参考1、RRT*-SMART: A Rapid Convergence Implementation of RRT*2、Rapid convergence implementation of RRT* towards optimal solution
7.1 原理 RRT*是一种基于采样的最优化路径规划方式，与RRT的区别是，RRT尽量使新节点以及其周围的节点到起点的cost(可以是路径或者时间等目标函数)最短，而不是仅仅寻找离它近的节点，而且在找到路径后不会停止，而是继续进行采样来优化得到的路径。 尽管RRT算法是一个相对高效率，同时可以较好的处理带有非完整约束的路径规划问题的算法，并且在很多方面有很大的优势，但是RRT算法并不能保证所得出的可行路径是相对优化的。因此许多关于RRT算法的改进也致力于解决路径优化的问题，RRT*算法就是其中一个。RRT*算法的主要特征是能快速的找出初始路径，之后随着采样点的增加，不断地进行优化直到找到目标点或者达到设定的最大循环次数。RRT*算法是渐进优化的，也就是随着迭代次数的增加，得出的路径是越来越优化的，而且永远不可能在有限的时间中得出最优的路径。因此换句话说，要想得出相对满意的优化路径，是需要一定的运算时间的。所以RRT*算法的收敛时间是一个比较突出的研究问题。但不可否认的是，RRT*算法计算出的路径的代价相比RRT来说减小了不少。RRT*算法与RRT算法的区别主要在于两个针对新节点 xnew 的重计算过程，分别为：·重新为 xnew 选择父节点的过程·重布线随机树的过程7.1.1 重新选择父节点过程 在新产生的节点 xnew 附近以定义的半径范围内寻找“近邻”，作为替换 xnew 父节点的备选。依次计算“近邻”节点到起点的路径代价加上 xnew 到每个“近邻”的路径代价，具体过程见上图。 图(a)中表现的是随机树扩展过程中的一个时刻，节点标号表示产生该节点的顺序，0节点是初始节点，9节点是新产生的节点 xnew，6节点是产生9节点的 xnear，节点与节点之间连接的边上数字代表两个节点之间的欧氏距离(这里我们用欧氏距离来表示路径代价)。 在重新找父节点的过程中，以9节点 xnew 为圆心，以事先规定好的半径，找到在这个圆的范围内 xnew 的近邻，也就是4，5，8节点。 原来的路径0 - 4 - 6 - 9代价为10 + 5 + 1 = 16，备选的三个节点与 xnew 组成的路径0 - 1 - 5 - 9，0 - 4 - 9和0 - 1 - 5 - 8 - 9代价分别为3 + 5 + 3 = 11，10 + 4 = 14和3 + 5 + 1 + 3 = 12，因此如果5节点作为9节点的新父节点，则路径代价相对是最小的，因此我们把9节点的父节点由原来的节点4变为节点5，则重新生成的随机树如图(b)所示。7.1.2 重布线随机树过程 在为xnew 重新选择父节点之后，为进一步使得随机树节点间连接的代价尽量小，为随机树进行重新布线。过程示意如上图重布线的过程也可以被表述成：如果近邻节点的父节点改为 xnew 可以减小路径代价，则进行更改。 如图(c)，9节点为新生成的节点 xnew ，近邻节点分别为节点4 , 6 , 8 。它们父节点分别为节点0 , 4 , 5。路径分别为0 - 4，0 - 4 - 6，0 - 1 - 5 - 8，代价分别为10，10 + 5 = 15 和3 + 5 + 1 = 9。 如果将4节点的父节点改为9节点 xnew ，则到达节点4的路径变为0 - 1 - 5 - 9 - 4，代价为3 + 5 + 3 + 4 = 15 大于原来的路径代价10，因此不改变4节点的父节点。 同理，改变了8节点的父节点，路径代价将由原来的9变为14，也不改变8节点的父节点。如果改变6节点的父节点为 xnew 则路径变为0 - 1 - 5 - 9 - 6，代价为3 + 5 + 3 + 1 = 12小于原来的路径代价15，因此将6的父节点改为节点9，生成的新随机树如图(d)。 重布线过程的意义在于每当生成了新的节点后，是否可以通过重新布线，使得某些节点的路径代价减少。如果以整体的眼光看，并不是每一个重新布线的节点都会出现在最终生成的路径中，但在生成随机树的过程中，每一次的重布线都尽可能的为最终路径代价减小创造机会。 RRT*算法的核心在于上述的两个过程：重新选择父节点和重布线。这两个过程相辅相成，重新选择父节点使新生成的节点路径代价尽可能小，重布线使得生成新节点后的随机树减少冗余通路，减小路径代价。7.2 伪码7.3 程序示例7.4 参考1、Sampling-based Algorithms for Optimal Motion Planning2、https://blog.csdn.net/weixin_43795921/article/details/88557317#t03、https://zhuanlan.zhihu.com/p/51087819
6.1原理 Dynamic RRT和Extended RRT一样，也是用来解决动态路径规划问题，它们的思想有一点是共通的，那就是不要完全放弃初始RRT生成的树或初始路径的信息，而是在此基础上重新规划。Dynamic RRT和Extended RRT的区别在于，Extended RRT利用的是RRT生成的初始路径的信息，而Dynamic RRT利用的是RRT生成的初始RRT树的信息。思路如下： 在老地图中，用RRT算法生成了一个RRT树，在新地图中，原始RRT树的节点信息（坐标、父节点）存储在一个节点集合中。在新地图中，先检测新地图中比老地图多出的障碍物，然后，以碰撞检测为评判根据，删除老节点集合中与新障碍物无法通过碰撞检测的节点和边。的到一颗修建过后的与新地形无碰撞的修剪后RRT树，然后再在这颗修剪后的额RRT树的基础上，继续生长这棵树，直到这棵树连接起点和终点，然后回溯路径，得出新路径。①从从初始配置到目标配置生成的 RRT 开始（图（a））。 ②当配置空间发生变化时（例如通过接收新信息），将RRT中因这些变化而失效的所有部分标记为无效（图（b）和（c））。 ③然后我们修剪树以去除所有这些无效部分（图（d））。 ④此时，保证树中剩余的所有节点和边都是有效的，但树可能不再达到目标。最后，我们把树长出来，直到再次达到目标6.2 伪码6.3 程序示例加入新的障碍物后，被该障碍物折断的剩余的图：在原来的树的基础上，继续生长后的图：6.4 参考Replanning with RRTs
公众号