A subspace approach to balanced truncation for model reduction of nonlinear control systems

In this paper, we introduce a new method of model reduction for nonlinear control systems. Our approach is to construct an approximately balanced realization. The method requires only standard matrix computations, and we show that when it is applied to linear systems it results in the usual balanced truncation. For nonlinear systems, the method makes use of data from either simulation or experiment to identify the dynamics relevant to the input–output map of the system. An important feature of this approach is that the resulting reduced‐order model is nonlinear, and has inputs and outputs suitable for control. We perform an example reduction for a nonlinear mechanical system. Copyright © 2002 John Wiley & Sons, Ltd.     

A spatio-temporal Volterra modeling approach for a class of distributed industrial processes

It is difficult to model a distributed parameter system (DPS) due to the infinite-dimensional time/space nature and unknown nonlinear uncertainties. A low-dimensional and simple nonlinear model is often required for practical applications. In this paper, a spatio-temporal Volterra model is proposed with a series of spatio-temporal kernels for modeling unknown nonlinear DPS. To estimate these kernels, they are expanded onto spatial and temporal bases with unknown coefficients. To reduce the model dimension and parametric complexity in the spatial domain, the Karhunen–Loève (KL) method is used to find the dominant spatial bases. To reduce the parametric complexity in the temporal domain, the Laguerre polynomials are selected as temporal bases. Next, using the Galerkin method, this spatio-temporal modeling becomes a linear regression problem. Then unknown parameters can be easily estimated using the least-squares method in the temporal domain. After the time/space synthesis, the spatio-temporal Volterra model can be constructed. The convergence of parameter estimation can be guaranteed under certain conditions. This model has a low-dimensional and simple nonlinear structure, which is useful for the prediction and control of the DPS. The simulation and experiment demonstrate the effectiveness of the proposed modeling method.     

Improved dynamic programming and approximation results for the knapsack problem with setups

In this paper, we consider the 0–1 knapsack problem with setups. Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm that performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an Integer Linear Programming (ILP) solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases that still permit fully polynomial‐time approximation schemes and others where the problem remains hard to approximate.     

Wartime logistics model for multi‐support unit location–allocation problem with frontline changes

To reflect a realistic, changing front line, wartime logistics are illustrated by a dynamic location–allocation model. In this paper, a mixed integer programming (MIP) model is developed for use in deciding the timing of unit relocation for continuous resupply, safe locations for support units, and delivery amounts that minimize total risk to the logistics service. Total risk in wartime logistics is represented by unsatisfied demand, hazard at the support site, and the number of relocations. The proposed MIP model reflects realistic factors in battle situations, such as maximum distance, vehicle capacity, basic load carried by combat units, and limited supplies during unit relocation. Furthermore, special operators for crossover and mutation are developed to maintain feasibility of possible solutions, and an efficient hybrid genetic algorithm is proposed to find optimal and near‐optimal solutions.     

Computing Local Signed Distance Fields for Large Polygonal Models

The signed distance field for a polygonal model is a useful representation that facilitates efficient computation in many visualization and geometric processing tasks. Often it is more effective to build a local distance field only within a narrow band around the surface that holds local geometric information for the model. In this paper, we present a novel technique to construct a volumetric local signed distance field of a polygonal model. To compute the local field efficiently, exactly those cells that cross the polygonal surface are found first through a new voxelization method, building a list of intersecting triangles for each boundary cell. After their neighboring cells are classified, the triangle lists are exploited to compute the local signed distance field with minimized voxel‐to‐triangle distance computations. While several efficient methods for computing the distance field, particularly those harnessing the graphics processing unit's (GPU's) processing power, have recently been proposed, we focus on a CPU‐based technique, intended to deal flexibly with large polygonal models and high‐resolution grids that are often too bulky for GPU computation.     

A Safe-Control Paradigm for Human–Robot Interaction

This paper introduces a new approach to control a robot manipulator in a way that is safe for humans in the robot's workspace. Conceptually the robot is viewed as a tool with limited autonomy. The limited perception capabilities of automatic systems prohibits the construction of failsafe robots of the capability of people Instead, the goal of our control paradigm is to make the interaction with a robot manipulator safe by making the robot's actions predictable and understandable to the human operator. At the same time the forces the robot applies with any part of its body to its environment have to be controllable and limited. Experimental results are presented of a human-friendly robot controller that is under development for a Barrett Whole Arm Manipulator robot.     

海洋机器人动态定位的坐标变换与系统结构

本文给出海洋机器人的原理性流体动力学模型.动态定位的基本定义,海洋机器人既定向又定位的坐标变换与系统结构,和只定位不定向的坐标变换与系统结构.     

Model Predictive Control for Nonlinear Distributed Parameter Systems based on LS‐SVM

This paper presents a novel model predictive control configuration for nonlinear distributed parameter systems based on least squares support vector machine. First, a data‐based modeling methodology for an unknown nonlinear distributed parameter system is introduced. Subsequently, the model predictive control framework based on the aforementioned model is presented at the measured point. To verify the effectiveness and feasibility of the control arithmetic, simulation results from a tubular reactor with the controller designed by the presented procedure are given.     

A Structured Synchronization and Communication Model Fitting Irregular Data Accesses

In this paper, we present a parallel programming and execution model based on alogicalordering of control flows. We show that it is possible to provide a unifying framework consisting of a synchronous programming model, thereby facilitating the mastery of programs, and an asynchronous execution model yielding efficient executions. Our approach is based on a SPMD and task parallel programming language, called –Chan. Communications take place through channels and rely on explicit send/receive instructions. In contrast to classical message passing models, synchronizations and communications are dissociated. We show that it is possible to perform a data-driven automatic translation of sequential and arbitrary DOACROSS loops into –Chan, by using nonmatching send/receive instructions. Our parallelization technique allows us to handle irregular control and leads to optimizations of communications in irregular computations.     

电梯规划的动态模型

讨论了写字楼上下班高峰期的电梯规划问题。首先提出了电梯方案的衡量标准,然后建立了一个比较完整的“动态规划”模型,对模型进行了求解。最后,对结果作了进一步的讨论,讨论了该模型对一般建筑以及超高建筑规划时候结果的不同,并回过头来验证了衡量标准的正确性。最后根据一个实际问题给出解决的方案。     

Online adaptive algorithm for optimal control with integral reinforcement learning

In this paper, we introduce an online algorithm that uses integral reinforcement knowledge for learning the continuous‐time optimal control solution for nonlinear systems with infinite horizon costs and partial knowledge of the system dynamics. This algorithm is a data‐based approach to the solution of the Hamilton–Jacobi–Bellman equation, and it does not require explicit knowledge on the system's drift dynamics. A novel adaptive control algorithm is given that is based on policy iteration and implemented using an actor/critic structure having two adaptive approximator structures. Both actor and critic approximation networks are adapted simultaneously. A persistence of excitation condition is required to guarantee convergence of the critic to the actual optimal value function. Novel adaptive control tuning algorithms are given for both critic and actor networks, with extra terms in the actor tuning law being required to guarantee closed loop dynamical stability. The approximate convergence to the optimal controller is proven, and stability of the system is also guaranteed. Simulation examples support the theoretical result. Copyright © 2013 John Wiley & Sons, Ltd.     

Remarks on the application of dynamic programming to the optimal path timing of robot manipulators

In this paper, we investigate the use of the dynamic programming approach in the solution of the optimal path timing problem in robotics. This problem is computationally feasible because the path constraint reduces the dimension of the state in the problem to two. The Hamilton–Jacobi–Bellman equation of dynamic programming, a nonlinear first order partial differential equation, is presented and is solved approximately using finite difference methods. Numerical solution of this results in the optimal policy which can then be used to define the optimal path timing by numerical integration. Issues relating to the convergence of the numerical schemes are discussed, and the results are applied to an experimental SCARA manipulator. © 1998 John Wiley & Sons, Ltd.     

High‐level specifications for automatically generating parallel code

The arrival of multicore systems, along with the speed‐up potential available in graphics processing units, has given us unprecedented low‐cost computing power. These systems address some of the known architecture problems but at the expense of considerably increased programming complexity. Heterogeneity, at both the architectural and programming levels, poses a great challenge to programmers. Many proposals have been put forth to facilitate the job of programmers. Leaving aside proposals based on the development of new programming languages because of the effort this represents for the user (effort to learn and reuse code), the remaining proposals are based on transforming sequential code into parallel code, or on transforming parallel code designed for one architecture into parallel code designed for another. A different approach relies on the use of skeletons. The programmer has available set of parallel standards that comprise the basis for developing parallel code while programming sequential code. In this context, we propose a methodology for developing an automatic source‐to‐source transformation in a specific domain. This methodology is instantiated in a framework aimed at solving dynamic programming problems. Using this framework, the final user (a physician, mathematician, biologist, etc.) can express her problem using an equation in Latex, and the system will automatically generate the optimal parallel code for homogeneous or heterogeneous architectures. This approach allows for great portability toward these new emerging architectures and for great productivity, as evidenced by the computational results.Copyright © 2012 John Wiley & Sons, Ltd.     

Hybrid approaches for the two‐scenario max–min knapsack problem

In this paper, we deal with the two‐scenario max–min knapsack (MNK) problem. First, we consider several formulations of MNK as a mixed integer programming problem. Then, we propose a hybrid method as an alternative to solve the MNK exactly. The approach combines relaxation technique and the temporary setting of variables to improve iteratively two sequences of upper and lower bounds. More precisely, pseudo‐cuts are added to the problem to strengthen the bounds and reduce the gap between the best lower bound and the best upper bound. The algorithm stops when the proof of the optimality of the best solution is found. We also use a reduction technique to set some variables definitively at their optimal values. Numerical experiments demonstrate the robustness of the approach. In particular, our algorithm is efficient to solve large and correlated instances of MNK.     

Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes

Membrane systems are biologically motivated theoretical models of distributed and parallel computing. In this paper, we present a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modified to solve general 0–1 integer programming problem.     

基于扫描匹配的室外环境SLAM 方法

针对室外环境中的机器人“绑架”问题,提出了基于地图匹配的SLAM方法．该方法舍弃了机器人里程计信息, 只利用局部地图和全局地图的图形相关性进行机器人定位．方法的核心是多重估计数据关联,并将奇异值分解应用到机器人位姿计算中．利用Victoria Park数据集将本算法与基于扩展卡尔曼滤波器的方法进行比较,实验结果证明了本文提出的算法的有效性．     

加速度空间中基于线性规划的移动机器人路径规划方法

针对动态不确定环境下移动机器人的路径规划问题, 提出了加速度空间中一种基于线性规划 (Linear programming, LP) 的方法. 在机器人的加速度空间中利用相对信息, 把机器人路径规划这一非线性问题, 描述成满足一组线性约束同时使目标函数极小的线性规划问题, 嵌入基于线性规划方法的规划器, 得到一条满足性能要求的最优路径. 仿真试验验证了算法的实用性及有效性, 与势场引导进化计算的方法 (Artificial potential guided evolution algorithm, APEA) 相比更优化, 更实时.     

An approximate dynamic programming approach to convex quadratic knapsack problems

Quadratic knapsack problem (QKP) has a central role in integer and combinatorial optimization, while efficient algorithms to general QKPs are currently very limited. We present an approximate dynamic programming (ADP) approach for solving convex QKPs where variables may take any integer value and all coefficients are real numbers. We approximate the function value using (a) continuous quadratic programming relaxation (CQPR), and (b) the integral parts of the solutions to CQPR. We propose a new heuristic which adaptively fixes the variables according to the solution of CQPR. We report computational results for QKPs with up to 200 integer variables. Our numerical results illustrate that the new heuristic produces high-quality solutions to large-scale QKPs fast and robustly.     

Online solution of nonlinear two‐player zero‐sum games using synchronous policy iteration

The two‐player zero‐sum (ZS) game problem provides the solution to the bounded L₂‐gain problem and so is important for robust control. However, its solution depends on solving a design Hamilton–Jacobi–Isaacs (HJI) equation, which is generally intractable for nonlinear systems. In this paper, we present an online adaptive learning algorithm based on policy iteration to solve the continuous‐time two‐player ZS game with infinite horizon cost for nonlinear systems with known dynamics. That is, the algorithm learns online in real time an approximate local solution to the game HJI equation. This method finds, in real time, suitable approximations of the optimal value and the saddle point feedback control policy and disturbance policy, while also guaranteeing closed‐loop stability. The adaptive algorithm is implemented as an actor/critic/disturbance structure that involves simultaneous continuous‐time adaptation of critic, actor, and disturbance neural networks. We call this online gaming algorithm ‘synchronous’ ZS game policy iteration. A persistence of excitation condition is shown to guarantee convergence of the critic to the actual optimal value function. Novel tuning algorithms are given for critic, actor, and disturbance networks. The convergence to the optimal saddle point solution is proven, and stability of the system is also guaranteed. Simulation examples show the effectiveness of the new algorithm in solving the HJI equation online for a linear system and a complex nonlinear system. Copyright © 2011 John Wiley & Sons, Ltd.     

基于0/1背包问题的算法探究

0／1背包问题是计算机科学中的一个经典问题。动态规划法，递归法，回溯法是求解该问题的三种典型方法，使用这三种方法求解0／1背包问题，并对各算法进行了理论分析。用不同规模的0／1背包问题对三种算法进行测试，比较它们的运行时间，发现测试结果与其理论分析结果相符．最后指出就求解不同规模的0／1背包问题而言各算法的优劣。