混合控制的有序迎风方法

### 混合控制的有序迎风方法 在控制理论领域，解决各种控制问题往往需要高效的数值方法。传统的迭代数值方法在求解耦合非线性方程时可能成本高昂，因此利用最优性原理构建快速数值方法成为研究的重要方向。本文将介绍一种用于混合控制问题的高效非迭代“有序迎风方法”（Ordered Upwind Methods，OUMs）。 #### 1. 引言 动态规划方法在处理离散、连续或混合控制问题时，依赖于某种形式的最优性原理。由此产生的价值函数方程通常是非线性且耦合的，使用迭代数值方法求解这些方程可能会非常昂贵。我们的目标是利用最优性原理，为控制理论中的方程构建快速数值方法。 本文引入了一系列高效的非迭代“有序迎风方法”（OUMs），用于解决广泛的混合控制问题。这些方法结合了离散因果关系（Dijkstra方法的基础）和连续各向异性控制问题的因果关系，计算复杂度为O(M log M)，其中M是用于离散化系统连续状态空间的网格点总数。 为了说明这些方法的应用，我们考虑一个旅行者在区域Ω中寻找到达预定目的地的最短时间问题。旅行者的速度可能取决于运动方向，同时区域中还存在从某些固定点到其他给定点的公交线路，这代表了叠加在连续域上的离散链接/转换。此外，还考虑了连续动力学对离散状态的依赖以及时间相关的动力学。 #### 2. 离散控制：Dijkstra方法 考虑网络上的离散最优轨迹问题，给定一个网络和每个节点相关的时间惩罚，全局最优轨迹问题是确定从起始节点到网络中某个出口集的最快路径。Dijkstra方法是解决此问题的经典算法，它用于计算从任何节点出发的最小退出时间，并且可以在O(M log M)次操作中获得解。 Dijkstra方法的时间惩罚不仅可以取决于特定节点，还可以取决于该节点中选择的特定链接，因此它适用于各向同性和各向异性控制问题。该方法是一种“单遍”算法，如果r是网络中节点的最大关联度，则网络上的每个点最多“更新”r次即可得到解。这种效率源于对信息传播方向的仔细利用，并且基于最优性原理。 下面简要总结Dijkstra方法： 1. **初始化**：将所有网格点分为三类：Far（未知U的正确值）、Accepted（已计算出U的正确值）和Considered（与Accepted相邻）。开始时，所有网格点都在Far类中，Uij = ∞。 2. **处理边界点**：将边界网格点（xij ∈ ∂Ω）移动到Accepted类中，Uij = q(xij)。 3. **初始化Considered点**：将与边界相邻的所有网格点移动到Considered类中，并根据公式Uij = min (Ui−1,j, Ui+1,j, Ui,j−1, Ui,j+1) + Cij计算Uij的临时值。 4. **选择最小U值的点**：在所有Considered点中找到U值最小的网格点xr。 5. **更新Accepted点**：将xr移动到Accepted类中。 6. **更新Considered点**：将与xr相邻的Far网格点移动到Considered类中。 7. **重新评估Considered点**：重新计算与xr相邻的所有Considered点的U值，如果新计算的值小于先前的临时值，则更新Uij。 8. **循环执行**：如果Considered类不为空，则返回步骤4。 该算法的计算复杂度为O(M log(M))，其中log(M)因子反映了维护一个排序的Considered值列表以确定下一个Accepted网格点的必要性。可以使用堆排序数据结构来高效实现该算法。 #### 3. 连续控制：有序迎风方法 对于连续最优控制问题，目标是找到从起始位置到出口集的最优路径。众所周知，随着网格细化，Dijkstra方法不会收敛到连续解。例如，在一个均匀笛卡尔网格上，每个节点的时间惩罚为常数C > 0，从起点到终点的最小时间是该网格上的曼哈顿距离乘以C，这与连续Eikonal问题的解不同。因此，Dijkstra方法不能用于获得连续问题的解。 ##### 3.1 各向同性连续控制问题的Dijkstra类求解器 在各向同性情况下，当速度仅取决于位置而不取决于运动方向时，有两种近期的算法，即Tsitsiklis方法和Sethian的快速行进方法，它们具有与Dijkstra方法相同的计算复杂度。这两种方法都利用了信息传播的信息来提高效率，因果关系允许以递增顺序构建解，从而产生了类似Dijkstra的解。 这两种算法都源于Eikonal方程的一个关键特征，即它们的特征线与粘性解u(x)的梯度线重合，这允许构建单遍算法。Tsitsiklis算法源于对各向同性最小时间最优轨迹问题的研究，涉及解决一个最小化问题来更新解；Sethian的快速行进方法源于对各向同性前沿传播问题的研究，涉及使用迎风有限差分公式来更新解。 ##### 3.2 一般各向异性连续控制问题的有序迎风方法 对于一般的连续最优轨迹问题，速度函数取决于位置和方向。Sethian和Vladimirsky构建并开发了用于各向异性连续最优控制问题的单遍“有序迎风方法”。他们证明了可以通过最多r次重新计算每个Ui来得到解，其中r仅取决于PDE中存在的各向异性程度和网格结构，而不取决于网格点的数量。 构建高效的单遍方法对于一般最优控制问题比Eikonal情况更具挑战性，因为特征线不再与粘性解的梯度线重合。因此，特征线和梯度线可能位于不同的单纯形中，这使得无法通过按升序计算/接受网格