Overapproximating Reachable Sets by Hamilton-Jacobi Projections

In earlier work, we showed that the set of states which can reach a target set of a continuous dynamic game is the zero sublevel set of the viscosity solution of a time dependent Hamilton-Jacobi-Isaacs (HJI) partial differential equation (PDE). We have developed a numerical tool—based on the level set methods of Osher and Sethian—for computing these sets, and we can accurately calculate them for a range of continuous and hybrid systems in which control inputs are pitted against disturbance inputs. The cost of our algorithm, like that of all convergent numerical schemes, increases exponentially with the dimension of the state space. In this paper, we devise and implement a method that projects the true reachable set of a high dimensional system into a collection of lower dimensional subspaces where computation is less expensive. We formulate a method to evolve the lower dimensional reachable sets such that they are each an overapproximation of the full reachable set, and thus their intersection will also be an overapproximation of the reachable set. The method uses a lower dimensional HJI PDE for each projection with a set of disturbance inputs augmented with the unmodeled dimensions of that projection's subspace. We illustrate our method on two examples in three dimensions using two dimensional projections, and we discuss issues related to the selection of appropriate projection subspaces.     

Solving awari with parallel retrograde analysis

A parallel search algorithm running on a large computer cluster solves a popular board game by computing the best moves from all reachable positions. The resulting databases contain scores for 889 billion positions.     

Under-estimates of reachable sets for linear control systems

A new algorithm is presented for providing under-estimates of the reachable set from the origin for a class ofn-dimensional linear systems with bounded controls. This algorithm is based on the novel approach of choosing a feedback control which makes all the eigenvalues of the closed loop system unstable. Results from feedback control and Liapunov stability theory are then used to formulate the problem as the minimization of a nonlinear function subject to constraints on certain matrices. The solution of this optimization problem provides an under-estimate of the reachable set in the form of ann-dimensional ellipsoid. Examples of both continuous and discrete-time systems are presented to illustrate the method. Comparison with existing exact results for some 2-dimensional systems shows that the method provides good approximations in these cases.     

一种求解线性控制系统可达集的数值方法

针对线性控制系统,研究应用常微分方程数值方法和优化技术相结合的近似可达集的方法.首先,用常微分方程数值方法对系统进行离散化.然后,提出基于优化技术的外部投影法来近似离散系统的可达集.外部投影法构造有限多个投影问题,每个都对应一个凸优化问题,通过求解这些凸优化问题最终可以得到可达集的近似描述.最后,通过数值仿真结果验证了所提出方法的有效性.与文献中已有的方法相比,在求解相同数量凸优化问题的情况下,外部投影法的近似精度更高.     

Measure-controlled dynamic systems: Polyhedral approximation of their reachable set boundary

An algorithm for polyhedral approximation of the reachable set of impulsive dynamic control systems is designed. The boundary points of the reachable set are determined by recursively generating and solving a family of auxiliary optimal impulsive control problems with state-linear objective functional. The impulsive control problem is solved with an algorithm that implicitly reduces the problem an ordinary optimal control problem. The reduced problem thus obtained is solved with an algorithm based on local approximations of the reachable set.     

泛集群环境中计算密集型任务流调度策略

针对计算节点较多的泛集群环境下难以快速、合理地制定计算密集型任务流调度方案的问题,提出一种基于多目标连续竞买博弈的任务调度策略.建立多目标优化调度模型,降低多目标优化函数维度,并采用线性加权和法将其转化为总和目标函数,以保证最优解的合理性.为提高最优解搜索速度,引入ETC矩阵作为最优解表达形式,设计连续竞买博弈算法.模拟真实场景并通过与同类算法的对比,表明了调度策略在泛集群环境下的响应速度、资源性价比和总成本支出等方面具有明显优势.     

基于时间线段树的城市可达区域搜索

针对城市计算中的可达区域搜索问题，提出一种基于时间线段树的搜索方法。该方法中，设计了存储局部可达区域的时间线段树结构，并提出动态自适应的可达区域搜索算法，从而提高了城市可达区域搜索的效率与准确率。该方法主要包括4个步骤：根据道路速度分布模型和轨迹数据生成道路段的概率时间权重；利用层级跳跃表算法进行短时间可达区域的查询与存储；利用时间线段树对层级可达区域建立高效的索引结构；使用时间线段树索引在道路网络中进行迭代搜索，最终输出可达区域集合。在北京市道路网络和出租车轨迹数据集上进行了大量实验，结果表明，与最新的单点上下界限区域可达查询（SQMB）方法比较，该方法在时间效率和准确率上分别提高了18.6%和25%。     

Hybrid control synthesis for eventuality specifications using level set methods

This paper is concerned with the extraction of controllers for hybrid systems with respect to eventuality specifications. Given a hybrid system modelled by a hybrid automaton and a target set of states, the objective is to compute the maximal set of initial states together with the hybrid control policy such that all the trajectories of the controlled system reach the target in finite time. Due to the existence of set-valued disturbance inputs, the problem is studied in a game-theoretic framework. Having shown that a least restrictive solution does not exist, we propose a dynamic programming algorithm that computes the maximal initial set and a controller with the desired property. To implement the algorithm, reachable sets of pursuit-evasion differential games need to be computed. For that reason level set methods are employed, where the boundary of the reachable set is characterized as the zero level set of a Hamilton–Jacobi equation. The procedure for the numerical extraction of the controller is presented in detail and examples illustrate the methodology. Finally, to demonstrate the practical character of our results, a control design problem in the benchmark system of the batch evaporator is considered as an eventuality synthesis problem and solved using the proposed methodology.     

基于时间线段树的城市可达区域搜索

针对城市计算中的可达区域搜索问题,提出一种基于时间线段树的搜索方法。该方法中,设计了存储局部可达区域的时间线段树结构,并提出动态自适应的可达区域搜索算法,从而提高了城市可达区域搜索的效率与准确率。该方法主要包括4个步骤：根据道路速度分布模型和轨迹数据生成道路段的概率时间权重;利用层级跳跃表算法进行短时间可达区域的查询与存储;利用时间线段树对层级可达区域建立高效的索引结构;使用时间线段树索引在道路网络中进行迭代搜索,最终输出可达区域集合。在北京市道路网络和出租车轨迹数据集上进行了大量实验,结果表明,与最新的单点上下界限区域可达查询（SQMB）方法比较,该方法在时间效率和准确率上分别提高了18.6%和25%。     

A robust Markov game controller for nonlinear systems

This paper proposes a reinforcement learning (RL)-based game-theoretic formulation for designing robust controllers for nonlinear systems affected by bounded external disturbances and parametric uncertainties. Based on the theory of Markov games, we consider a differential game in which a ‘disturbing’ agent tries to make worst possible disturbance while a ‘control’ agent tries to make best control input. The problem is formulated as finding a min–max solution of a value function. We propose an online procedure for learning optimal value function and for calculating a robust control policy. Proposed game-theoretic paradigm has been tested on the control task of a highly nonlinear two-link robot system. We compare the performance of proposed Markov game controller with a standard RL-based robust controller, and an H_∞ theory-based robust game controller. For the robot control task, the proposed controller achieved superior robustness to changes in payload mass and external disturbances, over other control schemes. Results also validate the effectiveness of neural networks in extending the Markov game framework to problems with continuous state–action spaces.     

基于可达集的鲁棒模型预测控制

设计了一种基于可达集的鲁棒模型预测控制算法.首先确定了一个鲁棒不变集,并将此不变集用作模型预测控制的终端约束集;接着采用终端约束集对可达集的包含度作为优化指标;最后,采用预测时域逐渐减小的控制策略以保证在线优化存在可行解.从理论上证明了吸引域内的任意点在有限时域内都会被引导至终端约束集并始终停留在此集之内,并由仿真算例验证了本文所设计鲁棒模型预测控制算法的可行性.     

Symbol recognition by error-tolerant subgraph matching betweenregion adjacency graphs

We propose an error-tolerant subgraph isomorphism algorithm formulated in terms of region adjacency graphs (RAG). A set of edit operations to transform one RAG into another one are defined as regions are represented by polylines and string matching techniques are used to measure their similarity. The algorithm follows a branch and bound approach driven by the RAG edit operations. This formulation allows matching computing under distorted inputs and also reaching a solution in a near polynomial time. The algorithm has been used for recognizing symbols in hand drawn diagrams     

基于Hamilton-Jacobi方程的飞行器机动动作可达集分析

为了给驾驶员完成标准机动动作提供决策支持, 提出一种使用哈密尔顿-雅克比(Hamilton-Jacobi)方程求解机动动作可行状态空间的研究方法.使用关键点将机动动作划分为不同阶段, 将各关键点的标准状态约束作为目标集, 逆时间求解目标集对应的可达集得到各阶段的边界状态范围, 目标集和可达集均由零水平集表示.使用该方法得到斤斗动作三维度运动模型下各阶段的可达集及斤斗动作的可行状态空间, 为了使运动模型的控制量与驾驶员实际操纵更为接近, 构建了以迎角变化率为控制量的四维度运动模型, 在此基础上对斤斗动作各阶段的可达集进行了分析.     

Tree regular model checking: A simulation-based approach

Regular model checking is the name of a family of techniques for analyzing infinite-state systems in which states are represented by words, sets of states by finite automata, and transitions by finite-state transducers. In this framework, the central problem is to compute the transitive closure of a transducer. Such a representation allows to compute the set of reachable states of the system and to detect loops between states. A main obstacle of this approach is that there exists many systems for which the reachable set of states is not regular. Recently, regular model checking has been extended to systems with tree-like architectures. In this paper, we provide a procedure, based on a new implementable acceleration technique, for computing the transitive closure of a tree transducer. The procedure consists of incrementally adding new transitions while merging states, which are related according to a pre-defined equivalence relation. The equivalence is induced by a downward and an upward simulation relation, which can be efficiently computed. Our technique can also be used to compute the set of reachable states without computing the transitive closure. We have implemented and applied our technique to various protocols.     

Web服务自动化测试技术

赋时Petri网为装配序列规划提供了有效的建模方法,但其在求解最优装配序列时受到组合复杂性的严重制约。零压缩二叉决策图(ZBDD)是处理大规模组合集合和0-1稀疏向量的一种有效符号技术,能够有效缓解组合爆炸问题。将赋时Petri网与ZBDD结合起来,给出了一种求解装配序列最优解的有效方法。首先通过转换算法将赋时Petri网转换为等价的普通Petri网,接下来给出普通Petri网可达状态及迁移引发函数的ZBDD表示方法,最后基于ZBDD给出最优装配序列求解算法。实例验证表明,该算法在求解过程中通过隐式符号操作实现了Petri网的可达状态搜索,有效缓解了计算过程中的组合复杂性。     

On continuous strategies of deviation from a nonconvex set under uncertainty conditions

Studies are made of continuous methods of the deviation in one differential game on the plane with a nonconvex terminal set. The game is nondegenerate in the sense that the programmed controls give no way of affording the deviation and there exists a (discontinuous) method of feedback control that guarantees the deviation. The problem under study can serve as an example of the nondegenerate differential game with a nonconvex terminal set, in which the attempt fails to assure the deviation with the aid of feedback control methods described by continuous mappings. Strategies are investigated that satisfy the Caratheodory conditions and contain the argument deviation. Despite the nonconvexity of the terminal set, by which the circumference serves, it is possible to perform the proof of the unsolvability with the aid of a rather simple mathematical technique on the basis of the Schauder theorem for the fixed point.     

一种面向严重受损路网的抢修队调度算法

受损路网抢修是灾害应急响应中的一个非常重要的基础环节,主要研究如何对道路抢修队进行有效调度,以快速恢复受灾路网的交通能力,为后续顺利展开应急救援工作提供有效的保证.已有方法在路网受损严重的情形下往往难以给出有效的调度策略.为此,在已有工作的基础上,简化路网模型和决策模型,并基于动作集裁减和Q学习设计一种面向严重受损路网的抢修队调度算法.在该算法中,抢修队只能从当前可达的未修复受损路段集合中选择下一个动作,以确保Q学习的连续性.仿真实验结果表明,在节点数和受损率都较大的严重受损路网环境中,所提算法可以保证所有需求节点均可达,具有更高的稳定性和可靠性,且能够在更小的时间和修复代价内给出更优的调度方案.     

Quadratic control of stochastic hybrid systems with renewal transitions

We study the quadratic control of a class of stochastic hybrid systems with linear continuous dynamics for which the lengths of time that the system stays in each mode are independent random variables with given probability distribution functions. We derive a condition for finding the optimal feedback policy that minimizes a discounted infinite horizon cost. We show that the optimal cost is the solution to a set of differential equations with unknown boundary conditions. Furthermore, we provide a recursive algorithm for computing the optimal cost and the optimal feedback policy. The applicability of our result is illustrated through a numerical example, motivated by stochastic gene regulation in biology.     

Improved LP-based algorithms for the closest string problem

In a recent paper by Liu et al. [Exact algorithm and heuristic for the closest string problem, Computers & Operations Research 2011;38:1513-20], a polynomial time heuristic procedure is proposed for the closest string problem (CSP). Such heuristic called LDDA_LSS is a combination of a previously published approximation algorithm and local search strategies. This paper points out that an instant algorithm deriving a feasible solution directly from the continuous relaxation solution of a standard ILP formulation of CSP already strongly outperforms LDDA_LSS both in terms of solution quality and computing time. Two core based procedures are then proposed that further improve the results of the instant algorithm. Based on these results, we conclude that such LP-based approaches for their efficiency and simplicity should be used as a benchmark for future heuristics on CSP.     

移动边缘计算中基于Stackelberg博弈的算力交易与定价

针对移动边缘计算中轻量级智能设备计算和存储能力有限等问题，提出一种基于Stackelberg博弈的计算卸载解决方案。首先，结合区块链技术构建基于云挖掘机制的算力交易模型——CPTP-BSG，允许移动智能设备（矿工）将密集且复杂的计算任务卸载到边缘服务器；其次，将矿工与边缘计算服务提供商（ESP）之间的算力交易建模为一个两阶段的Stackelberg博弈过程，并构建矿工与ESP的预期利润函数；然后，使用逆向归纳法分别在统一定价和歧视性定价策略下分析纳什均衡解的存在性和唯一性；最后，提出一种低梯度迭代算法来实现矿工和ESP的利润最大化。实验结果证明了所提算法的有效性，并且与统一定价相比，歧视性定价更符合矿工的个性化算力需求，能达到更高的算力需求总量和ESP利润。