微分动态规划

2023-11-05

from：https://en.wikipedia.org/wiki/Differential_dynamic_programming

深入理解DDP

DDP是一种轨迹优化类别问题中的最优控制算法。这种算法在1966年被Mayne提出。

该算法使用动态模型(dynamics)以及代价函数(cost functions)的局部二次(locally-quadratic)模型，并且展现二次收敛(displays quadratic convergence)性质。它与Pantoja's step-wise Newton's method有很大关联。

Finite-horizon discrete-time problems

下面我们来看看所要研究的问题：

The dynamics:

$\mathbf {x} _{i+1}=\mathbf {f} (\mathbf {x} _{i},\mathbf {u} _{i})$

从状态x出发，使用控制序列 $\mathbf {U} \equiv \{\mathbf {u} _{0},\mathbf {u} _{1}\dots ,\mathbf {u} _{N-1}\}$ 直到horizon is reached。

$J_{0}(\mathbf {x} ,\mathbf {U} )=\sum _{i=0}^{N-1}\ell (\mathbf {x} _{i},\mathbf {u} _{i})+\ell _{f}(\mathbf {x} _{N}),$

其中 $\mathbf {x} _{0}\equiv \mathbf {x}$ ，这个最优控制问题的解就是要寻找一个最优控制序列来最小化上面的代价函数

\mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).

轨迹优化(Trajectory optimization)意味着对于某一个 $\mathbf {x} _{0}$ 找到一个 $\mathbf {U} ^{*}(\mathbf {x} )$ 使得代价函数最小，而不是对于所有可能的初始状态(rather than for all possible initial states)。

Dynamic programming

设 $\mathbf {U} _{i}$ 是控制序列中的一部分 $\mathbf {U} _{i}\equiv \{\mathbf {u} _{i},\mathbf {u} _{i+1}\dots ,\mathbf {u} _{N-1}\}$ ，并且定义 cost-to-go $J_{i}$ 作为从

$i$ 到 $N$ 的一个部分和代价。

$J_{i}(\mathbf {x} ,\mathbf {U} _{i})=\sum _{j=i}^{N-1}\ell (\mathbf {x} _{j},\mathbf {u} _{j})+\ell _{f}(\mathbf {x} _{N}).$

其中令 $V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})$ ，动态规划原理指的是在时间上backwards，并且每一次都是基于单个控制步来减少cost function的：

$V(\mathbf {x} ,i)=\min _{\mathbf {u} }[\ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)].$

这就是Bellman equation。

Differential dynamic programming

DDP是如何运行的呢？

它通过迭代运行backward pass和forward pass来进行规划求解的。

DDP proceeds by iteratively performing a backward pass on the nominal trajectory to generate a new control sequence, and then a forward pass to compute and evalute a new nominal trajectory.

首先，我们看看backward pass是一个什么样的东西。

在上面一节的Bellman方程中，需要最小化的项为：

$\ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)$

设 $Q$ 为该量在 $i$ -th $(\mathbf {x} ,\mathbf {u} )$ 处的变分：

${\begin{aligned}Q(\delta \mathbf {x} ,\delta \mathbf {u} )\equiv &\ell (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} )&&{}+V(\mathbf {f} (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} ),i+1)\\-&\ell (\mathbf {x} ,\mathbf {u} )&&{}-V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)\end{aligned}}$

（我们知道，变分为0时也就达到了极值）。

将该式展开为二阶形式（Taylor展开即可，比如先按delta_x展开，再按delta_u展开）：

$\approx {\frac {1}{2}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}^{\mathsf {T}}{\begin{bmatrix}0&Q_{\mathbf {x} }^{\mathsf {T}}&Q_{\mathbf {u} }^{\mathsf {T}}\\Q_{\mathbf {x} }&Q_{\mathbf {x} \mathbf {x} }&Q_{\mathbf {x} \mathbf {u} }\\Q_{\mathbf {u} }&Q_{\mathbf {u} \mathbf {x} }&Q_{\mathbf {u} \mathbf {u} }\end{bmatrix}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}$

为了方便，我们将i去掉，并且利用prime(单引号)表示下一个时间步 $V'\equiv V(i+1)$ ，该展开的系数分别为：

${\begin{alignedat}{2}Q_{\mathbf {x} }&=\ell _{\mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {u} }&=\ell _{\mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {x} \mathbf {x} }&=\ell _{\mathbf {x} \mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+V_{\mathbf {x} }'\cdot \mathbf {f} _{\mathbf {x} \mathbf {x} }\\Q_{\mathbf {u} \mathbf {u} }&=\ell _{\mathbf {u} \mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {u} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {u} }\\Q_{\mathbf {u} \mathbf {x} }&=\ell _{\mathbf {u} \mathbf {x} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {x} }.\end{alignedat}}$

关于 $\delta\mathbf{u}$ 最小化上面的二阶展开式，有

${\delta \mathbf {u} }^{*}=\operatorname {argmin} \limits _{\delta \mathbf {u} }Q(\delta \mathbf {x} ,\delta \mathbf {u} )=-Q_{\mathbf {u} \mathbf {u} }^{-1}(Q_{\mathbf {u} }+Q_{\mathbf {u} \mathbf {x} }\delta \mathbf {x} ),$

上面是通过线性二次最优问题的解得出，这里为什么要最小化变分呢？首先，上面的变分作为一个二次项形式，总是大于等于0的，我们并不去直接求解变分为0，而是最小化变分，这样的话假使变分不能为0，也即没有0解，同样也可以得到一个 $\delta\mathbf{u}$ 使得变分尽可能小，也就是代价函数的变化尽可能小，也即趋于收敛。

定义一个open-loop term $\mathbf {k} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }$ ，以及一个feedback gain term $\mathbf {K} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }$ ，将上面的最优 $\delta\mathbf{u}$ 代入上面的二次展开式中，可以得到：

${\begin{alignedat}{2}\Delta V(i)&=&{}-{\tfrac {1}{2}}Q_{\mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }\\V_{\mathbf {x} }(i)&=Q_{\mathbf {x} }&{}-Q_{\mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }\\V_{\mathbf {x} \mathbf {x} }(i)&=Q_{\mathbf {x} \mathbf {x} }&{}-Q_{\mathbf {x} \mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }.\end{alignedat}}$

实际上，这里的Delta_V是1的系数，Vx是delta_x的系数，Vxx是(delta_x)^2的系数。

然后，我们反复递归计算 $V(i)$ 的局部二次模型(local quadratic models)以及control modifications $\{\mathbf {k} (i),\mathbf {K} (i)\}$ ，from $i=N-1$ down to $i=1$ 。

上面这些也就组成了backward pass。

其中 $V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})$ 。

一旦上面的backward pass完成之后，我们就可以通过forward pass来计算一个新的轨迹(trajectory)：

${\begin{aligned}{\hat {\mathbf {x} }}(1)&=\mathbf {x} (1)\\{\hat {\mathbf {u} }}(i)&=\mathbf {u} (i)+\mathbf {k} (i)+\mathbf {K} (i)({\hat {\mathbf {x} }}(i)-\mathbf {x} (i))\\{\hat {\mathbf {x} }}(i+1)&=\mathbf {f} ({\hat {\mathbf {x} }}(i),{\hat {\mathbf {u} }}(i))\end{aligned}}$

backward pass 和 forward pass将会一直迭代，直到收敛。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

微分动态规划的相关文章

Jmeter 课程笔记（三）三种参数化方式

1 三种参数化方式 1 1读取文本方法1 CSVRead函数函数助手使用 CSVRead函数第一个参数为文本的路径第二个参数为读取文本的第几列列数从0开始文本的每一列之间只支持用逗号隔开点击生成拷贝字符串复制到想要替换的参数
.Net 开源框架

1 开源框架选择数据持久层Nhibernate和IbatisNet这两个都是非常优秀的数据持久层 Nhibernate是优秀的Hibernate的dotNet移植版本在开源社区具有非常高的人气 IbatisNet是Data Mapper
PAT 5 兔子繁衍问题

兔子繁衍问题 15 分一对兔子从出生后第3个月起每个月都生一对兔子小兔子长到第3个月后每个月又生一对兔子假如兔子都不死请问第1个月出生的一对兔子至少需要繁衍到第几个月时兔子总数才可以达到N对输入格式输入在一行中给出一个不超过
逻辑回归调参

逻辑回归是一种常用的二分类模型它可以用来预测一个观测值属于某一类的概率在训练逻辑回归模型时通常需要调参来获得最优的模型性能常见的调参方法包括正则化参数调参在逻辑回归中可以使用正则化来防止过拟合常用的正则化方法有 L1 正则化
java arrays函数_java 关于Arrays、Array函数

Arrays及Array 这两个类都包含了很多用来操作Java数组的静态函数分别定义如下 public final class Array extends Object public class Arrays extends Object
Springboot 项目搭建activiti流程项目demo

Springboot 项目搭建activiti流程项目demo 首先在pom文件中添加依赖
wireshared-protobuf：proto.c:1765: failed assertion \"(guint)hfindex < gpa_hfinfo.len\"

这个问题一般出现在TCP连接中会导致这个问题的原因基本上是和wireshared的粘包处理有关系一般是因为网络发送的包和抓包软件捕获的包错位了例如你发送4个包抓包软件可能捕获到3 4 5 6等个数不一定是4个如果发送的数据包是
Linux命令集合速览

ps process status 命令用于显示当前进程的状态类似于 Windows 的任务管理器 netstat 命令用于显示网络状态利用 netstat 指令可让你得知整个 Linux 系统的网络情况 df disk free 命令
linux环境中iostat命令的安装,解决-bash: iostat: command not found问题

需求说明今天在测试环境的主机上准备通过iostat来查看系统的io情况发现没有该命令 root testvm Packages iostat bash iostat command not found 问题解决 1 安装sysstat
tms xdata 中实现CRUD功能

1 创建vcl工程 2 放置edit button组件 3 创建和销毁的代码 uses XData Client private Client TXdataClient procedure TForm1 FormCreate Sender
小学生测验

关于这段代码数据存放在一个叫data的文件中增加了结构体排序对小学生们的成绩排名其他要求如同题干大一时写的版本没文件读写大三时写的在下面项目一小学生测验 16学时问题描述面向小学1 2年级学生随机选择两个整数的加减法
Go的for循环

在Go语言中循环是通过for关键字来实现的 Go语言提供了三种基本的循环方式 for循环 range循环和for range循环 for循环 for 初始化语句循环条件循环后执行语句循环体代码初始化语句用于初始化循环变量循环条件
单例模式详解，包括应用场景及懒汉式的线程安全问题

什么是单例模式所谓类的单例设计模式就是采取一定的方法保证在整个的软件系统中对某个类只能存在一个对象实例并且该类只提供一个取得其对象实例的方法如果我们要让类在一个虚拟机中只能产生一个对象我们首先必须将类的构造器的访问权限设置为pr
win操作iOS UI自动化（tidevice+appium）

1 安装 tidevice 使用命令 pip install tidevice 2 使用数据线连接手机打出命令 tidevice list查看连接状态和udid 若有信息返回则连上 3 输入启动命令启动wda包 tidevice u 设
Java链表-合并两个有序链表

如何将两个有序链表合成一个新的有序链表基本思想定义一个新链表定义一个新链表的指针tempNode 当合并的两个链表的头节点指针都不指向空时比较两个链表节点的值找到里面较小的值的地址让新链表的指针tempNode下一个节点指向该最
数据分析基础目录

自从大数据技术火热之后现在数据分析也火热了至少我就有两个女同事转数据分析失败哈不是我不帮她们实在是帮不动哈哈这两个人都是英语专业的一个是文学学士一个是文学硕士专业跨得太大了但是我想说我转数据分析肯定会成功的不因为别的
gitlab ci 使用

gitlab ce与gitlab runner使用采用docker方式运行gitlab ce 运行两个gitlab runner 一个运行在容器中另一个安装在宿主机上运行gitlab ce和gitlab runner容器下载镜像 d
【统计学习方法-李航-笔记总结】二、感知机（感知机的原始形式与对偶形式）

本文是李航老师统计学习方法第二章的笔记欢迎大佬巨佬们交流主要包括以下几部分 1 感知机模型 2 感知机策略 3 感知机算法 1 感知机模型感知机是二分类的线性分类模型其输入为实例的特征向量输出为实例的类别取 1和 1两个值
用OpenPose做一个运动量测量器

代码 https github com B C WANG AI Apps tree master openpose app MotionMeasure 通过openpose获得肢体关键点的位置信息利用脖子位置作为中心点求得相对位置然后用
Windows MYSQL跳过密码登录以及密码修改

MYSQL跳过密码登录以及密码修改 1 以管理员身份打开命令行输入命令 net stop mysql 如果不是管理员身份可能会出现如下错误 2 开启跳过密码验证登录的MySQL服务在命令行输入 mysqld console skip

随机推荐

神经网络是如何训练的,神经网络是怎么训练的

想要学习人工神经网络需要什么样的基础知识人工神经网络理论百度网盘下载链接提取码 rxlc简介本书是人工神经网络理论的入门书籍全书共分十章第一章主要阐述人工神经网络理论的产生及发展历史理论特点和研究方向第二章至第九章介绍人工
机械臂抓取前言

一机械臂的一些相关概念自由度除去末端执行器一个机械臂上有几个电机就是几自由度机械臂二机械臂的抓取流程 1 读取深度摄像头的数据 2 在摄像头传输过来的图像中识别要抓取的物体并且得到想要抓取物体的二维的像素坐标 3 将二维像素坐标
IDEA让包分层显示的方式

IDEA中java包分层显示的方式初次使用IDEA的朋友有部分的包显示是如此显示但是这么显示有时会因为包的同级显示使得包使得包的显示过多此时就可以改变显示的方式小齿轮 gt gt Flatten Packages Middle
usbcan系列便携式can分析仪

简介 USBCAN系列便携式CAN分析仪通过USB接口快速扩展一路CAN通道使接入CAN网络非常容易它具有一体式和小巧紧凑的外形特别适合于随身携带 CAN接口采用金升阳电源模块和信号隔离芯片实现2500V DC电气隔离 USB接口E
前端Vue自定义得分构成水平柱形图组件可用于系统专业门类得分评估分析

引入Vue自定义得分构成水平柱形图组件 cc horBarChart 随着技术的发展传统的开发方式使得系统的复杂度越来越高一个小小的改动或小功能的增加可能会导致整体逻辑的修改造成牵一发而动全身的情况为了解决这个问题我们采用了组件化
官方推荐U盘安装Ubuntu 10.10 方法

通用USB Installer是一个Linux系统安装器允许你从你的USB闪存驱动器选择安装一个Linux发行版通用USB安装器使用非常方便只需选择一个 Linux发行版的ISO文件和你的U盘便能进行安装 Universal USB
java用模板生成word(docx)文档(含动态表格)

生成word思路用WPS或者office编辑好word的样式然后另存为word xml文档将xml翻译为FreeMarker模板最后用java来解析FreeMarker模板并输出Docx 编辑好需要使用的word文档 1 把需要注入
在Linux上面如何部署jar包？

1 首先打开工具Xshell或者FinalShell 并登录 2 使用 ll 命令查看根目录文件确定jar包将要放到哪个位置使用cd 命令进入文件如 cd opt yt 3 新建文件传输可和本地关联 4 将jar包直接拖过去就行 5
树的遍历（中序，前序，后序）

与只有一种逻辑遍历它们的线性数据结构数组链表队列堆栈等不同树可以以不同的方式遍历常见的有中序遍历前序遍历和后序遍历实现各种遍历的方法又包括以上图为例深度优先遍历 a 中序左根右 4 2 5 1 3 b 前序根
关于async & await（TAP）异步模型的异常捕获

在TAP之前若要捕获线程中Task的异常通常有两种办法 1 阻塞线程开始后在适当的时机调用 wait 或waitAll方法 2 非阻塞推荐在建立任务的时候写该task的continueWith方法在该方法中捕获异常对于T
get提交和post提交的区别

Http定义了与服务器交互的不同方法最基本的方法有4种分别是GET POST PUT DELETE URL全称是资源描述符我们可以这样认为一个URL地址它用于描述一个网络上的资源而HTTP中的GET POST PUT DELET
Linux安装以及使用

Linux虚拟机安装以及使用 1 安装VMware16 2 创建虚拟机 3 虚拟机配置网络 4 利用mobaxterm连接服务器 5 配置jdk和tomcat 6 配置docker和mysql 7 部署项目 1 安装VMware16 接下来
leetcode160–相交链表（最优解/双指针）

今天做的三道题比较简单给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点如果两个链表不存在相交节点返回 null 题目数据保证整个链式结构中不存在环注意函数返回结果后链表必须保持其原
ISA(MIPS,ARM,RISC-V)中的算术运算溢出检测逻辑是怎样的？

关于ISA架构之前写过一些总结这里单独将其中一个技术点拿出来对比分析不同架构下实现的差异这个技术点就是算术指令中的溢出检测 ARM体系结构中通过CPSR的状态寄存器反映当前指令的溢出状态而MIPS 则是通过指令触发中断的方式产生
Jenkins使用(代码拉取-＞编译构建-＞部署上线)

Jenkins简介 Jenkins是一个开源项目提供了一种易于使用的持续集成系统使开发者从繁杂的集成中解脱出来专注于更重要的业务逻辑实现上同时Jenkins能实时监控集成中存在的错误提供详细的日志文件和提醒功能还能用图表的形式形
Java——(1)定义一个学生类Student，包含属性：姓名(String name)、年龄(int age) (2)定义Map集合，用Student对象作为key

分析以下需求并用代码实现 1 定义一个学生类Student 包含属性姓名 String name 年龄 int age 2 定义Map集合用Student对象作为key 用字符串此表示表示学生的住址作为value 3 利用四种方式
db2异常

一 db2 SQL0180N The syntax of the string representation of a datetime value is incorrect SQLSTATE 2200 问题描述在用import导入时没有
qt入门级使用

qt的安装可参考 QT下载安装及配置教程亲测好用 qt基本使用 1 创建第一个qt程序打开后欢迎界面如下这是关于qt的一些项目的讲解不过视频地址在国外需要翻qiang才能看而且全是英文左边还有一个示例那里面有各种项目的模
Android开发之RecyclerView的使用全解

转自 http blog csdn net dmk877 article details 50816933 自Android 5 0之后谷歌公司推出了RecylerView控件 RecylerView 我想看到一个新名词后大部分人会首先发
微分动态规划

from https en wikipedia org wiki Differential dynamic programming 深入理解DDP DDP是一种轨迹优化类别问题中的最优控制算法这种算法在1966年被Mayne提出该算法使

微分动态规划

微分动态规划 的相关文章

随机推荐

热门标签

微分动态规划的相关文章