Search

This work presents an online decentralized allocation algorithm of a safety-critical application on parallel computing architectures, where individual Computational Units can be affected by faults. The described method includes representing the architecture by an abstract graph where each node represents a Computational Unit. Applications are also represented by the graph of Computational Units they require for execution. The problem is then to decide how to allocate Computational Units to applications to guarantee execution of a safety-critical application. The problem is formulated as an optimization problem with the form of an Integer Linear Program. A state-of-the-art solver is then used to solve the problem. Decentralizing the allocation process is achieved through redundancy of the allocator executed on the architecture. No centralized element decides on the allocation of the entire architecture, thus improving the reliability of the system. Inspired by multi-core architectures in avionics systems, an experimental illustration of the work is also presented. It is used to demonstrate the capabilities of the proposed allocation process to maintain the operation of a physical system in a decentralized way while individual components fail.

This paper investigates stability analysis for implicit, switched linear systems using homogeneous Lyapunov functions (HLF). HLFs of increasing degree are constructed through an outer-product, lifting transformation of the state vector to higher dimensions. This paper presents linear matrix inequalities sufficient conditions for asymptotic stability of these systems based on HLFs. A method is provided to search for Lyapunov functions by incrementally increasing the degree of the homogeneous Lyapunov functions. To address the dimensional growth of the problem space incurred by the lifting transform, a method for dimensional reduction is derived.

Performance analysis for linear time-invariant (LTI) systems has been closely tied to quadratic Lyapunov functions ever since it was shown that LTI system stability is equivalent to the existence of such a Lyapunov function. Some metrics for LTI systems, however, have resisted treatment via means of quadratic Lyapunov functions. Among these, point-wise-in-time metrics, such as peak norms, are not captured accurately using these techniques, and this shortcoming has prevented the development of tools to analyze system behavior by means other than e.g. time-domain simulations. This work demonstrates how the more general class of homogeneous polynomial Lyapunov functions can be used to approximate point-wise-in-time behavior for LTI systems with reduced conservatism, and we extend this to the case of linear time-varying (LTV) systems as well. Our findings rely on the recent observation that the search for homogeneous polynomial Lyapunov functions for LTV systems can be recast as a search for quadratic Lyapunov functions for a related hierarchy of time-varying Lyapunov differential equations; thus, performance guarantees for LTV systems are attainable without heavy computation or additional algebraic developments. Numerous examples are provided to illustrate the findings of this work.

Stability margins for linear time-varying (LTV) and switched-linear systems are traditionally computed via quadratic Lyapunov functions, and these functions certify the stability of the system under study. In this work, we show how the more general class of homogeneous polynomial Lyapunov functions is used to compute stability margins with reduced conservatism, and we show how these Lyapunov functions aid in the search for periodic trajectories for marginally stable LTV systems. Our work is premised on the recent observation that the search for a homogeneous polynomial Lyapunov function for some LTV systems is easily encoded as the search for a quadratic Lyapunov function for a related LTV system, and our main contribution is an intuitive algorithm for generating upper and lower bounds on the system's stability margin. We show also how the worst-case switching scheme - which draws an LTV system closest to a periodic orbit - is generated. Three numerical examples are provided to aid the reader and demonstrate the theoretical contributions of the work.

The paper proposes a control-theoretic framework for verification of numerical software systems, and puts forward software verification as an important application of control and systems theory. The idea is to transfer Lyapunov functions and the associated computational techniques from control systems analysis and convex optimization to verification of various software safety and performance specifications. These include but are not limited to absence of overflow, absence of division-by-zero, termination in finite time, absence of dead-code, and certain user-specified assertions. Central to this framework are Lyapunov invariants. These are properly constructed functions of the program variables, and satisfy certain properties-analogous to those of Lyapunov functions-along the execution trace. The search for the invariants can be formulated as a convex optimization problem. If the associated optimization problem is feasible, the result is a certificate for the specification., National Science Foundation (U.S.) (Grant CNS-1135955), National Science Foundation (U.S.) (Grant CPS-1135843), United States. Army Research Office. Multidisciplinary University Research Initiative (Award W911NF-11-1-0046), United States. National Aeronautics and Space Administration (Grant/Cooperative Agreement NNX12AM52A)

The regulation of vehicle trajectories in the vicinity of obstacles must focus on “critical outputs,” which vary as a function of the vehicle's position relative to obstacles as exemplified by the task of parking a car. We present an application of linear parameter-varying techniques to address this problem. We design closed-loop stable, parameter-dependent controllers, whose strategy changes depending on the position of the vehicle in the obstacle environment. We also provide a fast and easy-to-implement algorithm for online controller construction. Last, the proposed approach is demonstrated on a three degrees-of-freedom helicopter.

We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically.

A set of N independent Gaussian linear time-in variant systems is observed by M sensors whose task is to provide a steady-state causal estimate minimizing the mean-square error on the system states, subject to additional measurement costs. The sensors can switch between systems instantaneously, and there are additional resource constraints, for example on the number of sensors that can observe a given system simultaneously. We first derive a tractable relaxation of the problem, which provides a bound on the achievable performance. This bound can be computed by solving a convex program involving linear matrix inequalities, and moreover this program can be decomposed into coupled smaller dimensional problems. In the scalar case with identical sensors, we give an analytical expression of an index policy proposed in a more general context by Whittle. In the general case, we develop open-loop periodic switching policies whose performance matches the bound arbitrarily closely.

This paper studies the conflict resolution for intersecting flows of mobile agents based on planar space partition. The idea of space partition is first demonstrated for two intersecting flows of mobile agents. Then, for three intersecting flows, where simple decentralized conflict avoidance rules may not handle all traffic scenarios, it is proved that certain periodic partitions of space are able to provide conflict resolution for any distribution of agents in the flows. A computational procedure based on mixed integer programming is further proposed to find optimal space partitions. The approach of space partition is not an online optimization algorithm. An online algorithm may find optimal resolution of conflict for a specific set of mobile agents but has to be rerun each time when new agents arrive, whereas a periodic partition of space provides a priori geometrical configuration for conflict avoidance regardless of the number and arriving patterns of the agents. Moreover, the offline nature of space partition does not imply a decrease of performance. As demonstrated in an example involving three symmetrically arranged agent flows, the optimal space partition has found a tight upper bound for the magnitude of any conflict-free maneuvers.

A technique is presented for creating continuously parameterized classes of feasible system trajectories. These classes, which are useful for higher-level vehicle motion planners, follow directly from a small collection of userprovided example motions. A dynamically feasible trajectory interpolation algorithm generates a continuous family of vehicle maneuvers across a range of boundary conditions while enforcing nonlinear system equations of motion as well as nonlinear equality and inequality constraints. The scheme is particularly useful for describing motions that deviate widely from the range of linearized dynamics and where satisfactory example motions may be found from off-line nonlinear programming solutions or motion capture of human-piloted flight. The interpolation algorithm is computationally efficient, making it a viable method for real-time maneuver synthesis, particularly when used in concert with a vehicle motion planner. Experimental application to a three-degree-of-freedom rotorcraft test bed demonstrates the essential features of system and trajectory modeling, maneuver example selection, maneuver class synthesis, and integration into a hybrid system path planner.

In this paper, we introduce an approach for the efficient solution of motion-planning problems for time-invariant dynamical control systems with symmetries, such as mobile robots and autonomous vehicles, under a variety of differential and algebraic constraints on the state and on the control inputs. Motion plans are described as the concatenation of a number of well-defined motion primitives, selected from a finite library. Rules for the concatenation of primitives are given in the form of a regular language, defined through a finite-state machine called a Maneuver Automaton. We analyze the reachability properties of the language, and present algorithms for the solution of a class of motion-planning problems. In particular, it is shown that the solution of steering problems for nonlinear dynamical systems with symmetries and invariant constraints can be reduced to the solution of a sequence of kinematic inversion problems. A detailed example of the application of the proposed approach to motion planning for a small aerobatic helicopter is presented.

We propose an alternative to gain scheduling for stabilization of nonlinear systems. For a useful class of nonlinear systems, the characterization of a region of stability based on a control Lyapunov function is computationally tractable, in the sense that computation times vary polynomially with the state dimension for a fixed number of scheduling variables. Using this fact, we develop a procedure to expand the region of stability by constructing control Lyapunov functions to various trim points of the system. A Lyapunov-based control synthesis algorithm is used to construct a control law that guarantees closed-loop stability for initial conditions in the expanded region of state space. This control asymptotically recovers the optimal stability margin in the sense of a Lyapunov derivative, which in turn can be seen as a performance measure. Robustness to bounded disturbances and stabilization under bounded control are easily incorporated into this framework. In the worst case, the computational complexity of the analysis problem that develops in the new method is increased by an exponential in the disturbance dimension. Similarly, we can handle control constraints with an increase in computational complexity of no more than an exponential in the control dimension. We demonstrate the new control design procedure on an example.

Nonlinear control systems can be stabilized by constructing control Lyapunov functions and computing the regions of state space over which such functions decrease along trajectories of the closed-loop system under an appropriate control law. This paper analyzes the computational complexity of these procedures for two classes of control Lyapunov functions. The systems considered are those which are nonlinear in only a few state variables and which may be affected by control constraints and bounded disturbances. This paper extends previous work by the authors, which develops a procedure for stability analysis for these systems whose computational complexity is exponential only in the dimension of the "nonlinear" states and polynomial in the dimension of the remaining states. The main results are illustrated by a numerical example for the case of purely quadratic control Lyapunov functions.

Nonlinear control systems can be stabilized by constructing control Lyapunov functions and computing the regions of state space over which such functions decrease along trajectories of the closed loop system under an appropriate control law. For systems whose dynamics are nonlinear in only a few state variables, we develop a method for computing such a region based on a given polytopic control Lyapunov function. The procedure is computationally tractable, in the sense that computation times vary polynomially with the state dimension for a fixed number of "nonlinear states". Control constraints and robustness to bounded disturbances are easily incorporated into this framework.

We consider the problems of robust stability and performance analysis of linear systems subject to parametric uncertainties. The Popov criterion provides lower bounds of stability margins and upper bounds on robust performance. In this paper we propose a method for obtaining upper bounds on stability margin or lower bounds on robust H2 performance based on the outcome of the lower bound computation for the stability problem or the upper bound computation for the H2 performance problem. We make several numerical tests.

In this paper, the problem of determining the worst-case H2 performance of a control system subject to linear time-invariant uncertainties is considered. A set of upper bounds on the performance is derived, based on the theory of stability multipliers and the solution of an original optimal control problem. The numerical issues raised by the resulting computational problems are discussed; in particular, newly developed interior-point convex optimization methods, combined with linear matrix inequalities, apply very well to the fast and accurate solution of these problems. The new results compare favorably with prior ones. The method can be extended to other types of perturbations.

In this paper, the problem of robust stability of systems subject to parametric uncertainties is considered. Sufficient conditions for the existence of parameter-dependent Lyapunov functions are given in terms of a criterion which is reminiscent of, but less conservative than, Popov's stability criterion. An equivalent frequency-domain criterion is demonstrated. The relative sharpness of the proposed test and existing stability criteria is then discussed. The use of parameter-dependent Lyapunov functions for robust controller synthesis is then considered. It is shown that the search for robustly stabilizing controllers may be limited to controllers with the same order as the original plant. A possible synthesis procedure and a numerical example are then discussed.

Embedded system control often relies on linear systems, which admit quadratic invariants. The parts of the code that host linear system implementations need dedicated analysis tools, since intervals or linear abstract domains will give imprecise results, if any at all, on these systems. Previous work by FERET proposes a specific abstraction for digital filters that addresses this issue on a specific class of controllers.This paper aims at generalizing the idea. It works directly on system representation, relying on existing methods from control theory to automatically generate quadratic invariants for linear time invariant systems, whose stability is provable. This class encompasses n-th order digital filters and, in general, controllers embedded in critical systems.While control theorists only focus on the existence of such invariants, this paper proposes a method to effectively compute tight ones. The method has been implemented and applied to some benchmark systems, giving good results. It also considers floating points issues and validates the soundness of the computed invariants.

We investigate a state feedback Linear Quadratic Regulation problem with a constraint on the number of actuation signals that can be updated simultaneously. Such a constraint arises for example in networked and embedded control systems, due to limited communication and computation capabilities. Following recent results on the dual problem of scheduling Kalman filters, we first develop a bound on the achievable performance that can be computed efficiently by semidefinite programming. This bound can be approached arbitrarily closely by an analog periodic controller that can switch between control inputs arbitrarily fast. We then discuss implementation issues on digital platforms, i.e., the discretization of the analog controller in the presence of a relatively fast but finite sampling rate.

The paper presents a parameter-dependent Lyapunov approach for the control of nonstationary and hybrid linear-parameter varying (LPV) systems. The work is motivated by the challenges encountered in controlling nonlinear systems about aggressive trajectories, specifically pre-specified eventually periodic ones.

A set of N independent Gaussian linear time invariant systems is observed by M sensors whose task is to provide the best possible steady-state causal minimum mean square estimate of the state of the systems, in addition to minimizing a steady-state measurement cost. The sensors can switch between systems instantaneously, and there are additional resource constraints, for example on the number of sensors which can observe a given system simultaneously. We first derive a tractable relaxation of the problem, which provides a bound on the achievable performance. This bound can be computed by solving a convex program involving linear matrix inequalities. Exploiting the additional structure of the sites evolving independently, we can decompose this program into coupled smaller dimensional problems. In the scalar case with identical sensors, we give an analytical expression of an index policy proposed in a more general context by Whittle. In the general case, we develop open-loop periodic switching policies whose performance matches the bound arbitrarily closely., 30 pages, 1 figure

In previous works, the authors introduced a framework for software analysis, which is based on optimization of Lyapunov invariants. These invariants prove critical software properties such as absence of overflow and termination in finite time. In this paper, graph models of software are introduced and the software analysis framework is further developed and extended on graph models. A distributed Lyapunov function is assigned to the software by assigning a Lyapunov function to every node on its graph model. The global decremental condition is then enforced by requiring that the Lyapunov functions on each node decrease as transitions take place along the arcs. The concept of graph reduction and optimality of graphs for Lyapunov analysis is briefly discussed.

Multi-agent systems are in general believed to be more efficient, robust, and versatile than their single-agent equivalents. However, it is not an easy task to design strategies that fully exploit the multi-agent benefits, and with this in mind we address several multi-agent system design issues. Specifically, it is of central importance to determine the optimal agent group composition, which involves a trade-off between the cost and performance increase per additional agent. Further, truly autonomous agents solely rely on on-board environment measurements, the design of which requires quantifying the multi-agent performance as a function of the locally observed environment areas. In this thesis, we focus on the collaborative search for individually rewarding resources, i.e. it is possible for multiple agents to incur the same reward. The system objective is to maximize the aggregate rewards incurred. Motivated by a cooperative surveillance context, we formulate a graph traversal problem on an unbounded structured graph, and restrain the agent motion spatially so that only the lateral agent separation is controlled. We model the problem mathematically as a discrete, infinite state, infinite horizon Dynamic Program and convert it using standard techniques to an equivalent Linear Program (LP) with infinitely many constraints. The graph spatial invariance allows to decompose the LP into a set of infinitely many coupled LPs, each with finitely many constraints. We establish that the unique bounded function that simultaneously satisfies the latter LPs is the problem optimal value function. Based on this, we compute the two-agent optimal value function explicitly as the solution of an LP with finitely many constraints for small agent separations, and implicitly in the form of a recursion for large agent separations, satisfying adequate connection constraints. Finally, we propose a similar method to compute the state probability distribution in steady state under an optimal policy, summarizing the agent behavior at large separations in a set of connection constraints, which is sufficient to compute the probability distribution at small separations. We analyze and compare the optimal performance of various problem instances. We confirm and quantify the intuition that the performance increases with the group size. Some results stand out: for cone-shaped local observation, two agents incur 25% less cost than a single agent in a mine field type environment (scarce though high costs); further, for some environment specifics, a third agent provides little to no performance increase. Then, we compare various local observation zones, and quantify their effect on the overall group performance. Finally, we study the agent spatial distribution under an optimal policy, and observe that as rewards are scarcer, the agents tend to spread in order to gather information on a larger environment part. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)

We consider the problem of finding optimal realizations of discrete-time digital filters w.r.t. implementation on a finite-memory machine with a fixed-point processor. A realization for which the performance of the fixed-point implementation under quantization effects is closest (in some sense) to the ideal performance (assuming precise arithmetic) is considered optimal. The transfer function corresponding to the optimal implementation is not necessarily the same as the transfer function of the original filter. Therefore, the optimal implementation cannot be obtained via a change of coordinates. This problem is inherently a nonlinear control problem due to the presence of the quantizer. We use a signal + noise model to linearize the system. After linearization, the problem of finding the optimal realization is still a nonconvex optimization problem. We show that under some mild technical assumptions the problem can be convexified losslessly, and transformed into an equivalent set of LMIs for which numerical solutions can be obtained efficiently.

We consider algorithms for the curvature-constrained traveling salesman problem, when the nonholonomic constraint is described by Dubins' model. We indicate a proof of the NP-hardness of this problem. In the case of low point densities, i.e., when the Euclidean distances between the points are larger than the turning radius of the vehicle, various heuristics based on the Euclidean Traveling salesman problem are expected to perform well. In this paper we do not put a constraint on the minimum Euclidean distance. We show that any algorithm that computes a tour for the Dubins' vehicle following an ordering of points optimal for the Euclidean TSP cannot have an approximation ratio better than Omega(n), where n is the number of points. We then propose an algorithm that is not based on the Euclidean solution and seems to behave differently. For this algorithm, we obtain an approximation guarantee of O (min {(1+rho/epsiv)log n, (1+rho/epsiv)2), where rho is the minimum turning radius, and epsiv is the minimum Euclidean distance between any two points.

Iterative algorithms such as the Newton method or the steepest gradient method appear in real-time software to solve online optimization problems as part of autonomous decision making algorithms. Proving safety and in particular convergence properties of such methods in their generic form is hopeless. However, for a special class of problems over a limited range of inputs and uncertain parameters, such task may become possible. In this paper, we consider applications of the Newton method to polynomial root finding and suggest new methods, based on Lyapunov invariance analysis and sum of squares programming to prove convergence and other performance properties of such algorithms. Generic forms for such Lyapunov invariants are presented and it is shown how the search for the certificates of performance can be formulated as a sum of squares program. The proof methods can be automated and thus integrated within a verification and validation workspace for software verification.

The purpose of this paper is to give a historical view of linear matrix inequalities in control and system theory. Not surprisingly, it appears that LMIs have been,involved in some of the major events of control theory. With the advent of powerful convex optimization techniques, LMIs are now about to become an important practical tool for future control applications.

The problem of stabilizing a class of nonlinear plants via observer-based controllers is addressed. Quadratic Lyapunov functions are used to determine the existence of such controllers. Sufficient conditions for their existence are given in terms of linear matrix inequalities, thus providing effective means to determine if these controllers exist.

In this paper, the problem of robust stability of systems subject to parametric uncertainties is considered. Sufficient conditions for the existence of parameter-dependent Lyapunov functions are given in terms of a criterion which is reminiscent of but less conservative than Popov's stability criterion. It is shown how the so-called S-procedure plays a crucial role in the derivation of this criterion. A comparison with existing stability criteria is done. An equivalent frequency-domain criterion is given. Extensions to cover slowly time-varying systems and robust performance are given.

For linear systems with delays, the authors define a new class of Lyapunov-like functionals that can be used to prove stability. They also show how one can design a stabilizing (delayed) state feedback for delay systems using these functionals and convex optimization techniques. It is shown how the problem of the design of a stabilizing (delayed) state-feedback can be posed as a convex feasibility problem. >

Although the problem of finding a stabilizing state feedback for an LTI system has been solved, it is still not easy to control an uncertain LTI system by a single state feedback gain which stabilizes a finite number of plant configurations, each representing a particular operating point. Researchers have focused on finding sufficient conditions in order to obtain convex problems which are readily solvable by standard convex optimization methods. One approach uses the quadratic stability condition, i.e. one looks for a single quadratic Lyapunov function which proves the stability of all closed loop models. Although this problem can be easily solved, the resulting sufficient condition is conservative and is more suitable for systems which (rapidly) switch among a family of linear systems. Another sufficient condition, proposed by El Ghaoui, is also a convex one and can be written in terms of LMIs (1993). This condition does not require quadratic stability. In this paper, the authors propose a relaxation algorithm for finding one stabilizing state feedback gain by recasting the whole problem into two LMIs. When all the states are not available, this algorithm can also handle output feedback. Since seeking a dynamic feedback compensator is equivalent to looking for an output feedback for an augmented system, the proposed method can be used for dynamic compensation as well. Due to the flexibility of convex optimization methods, several constraints on the closed loop system performance, such as H/sub 2/, H/sub /spl infin// etc, can be incorporated in the design process.

This paper describes a method of generating continuously parametrized maneuver classes based on a finite number of user-provided examples motions. A trajectory interpolation algorithm performs a smooth transformation of vehicle maneuvers across a continuous range of boundary conditions while enforcing nonlinear system equations of motion as well as nonlinear equality and inequality constraints. The scheme is particularly useful for describing motions that deviate widely from the range of linearized dynamics and where satisfactory examples may be found from off-line nonlinear programming solutions or human pilot motion capture. The interpolation algorithm is computationally efficient, making it a suitable alternative for near real-time maneuver synthesis, particularly when used in concert with a vehicle motion planner. Experimental application to a three degree-of-freedom rotorcraft test bed demonstrates the essential features of system and trajectory modeling, maneuver example selection, maneuver class synthesis, and integration into a hybrid system path planner.

The receding horizon control (RHC) scheme uses online optimization to find a finite-horizon control input to a constrained dynamic system. This paper examines the relationship between the optimization algorithm and the closed-loop dynamic system in RHC. Past research on RHC has assumed that the optimization algorithm provides an optimal solution in a fixed time interval. Since RHC typically employs quadratic programming, which is usually solved only approximately, this presupposition is not valid. Instead of making the traditional optimality assumption, this paper supposes that the provided solutions are only suboptimal. A sufficient condition is derived for closed-loop stability given control sequences which are optimal with tolerance /spl epsiv/. Also, a bound is derived for the number of computations to find an /spl epsiv/-optimal solution from a warm start using an interior-point method. As long as this number of computations can be carried out in less than the time step of the dynamic system, the closed-loop is guaranteed to be stable.

In this paper, we examine the problem of determining the worst-case H/sub 2/ performance of a control system subject to linear, time-invariant uncertainties. We derive upper bounds on the performance, based on the theory of stability multipliers and the solution of an original optimal control problem. We address the numerical issues raised by the resulting computational problems: in particular, we show that newly developed interior-point convex optimization methods, combined with linear matrix inequalities apply very well to the fast and accurate solution of these problems. The new results compare favorably with prior ones. >

Two methods are presented for grouping actuators while minimizing performance degradation in distributed control systems with saturation constraints. Method one is based on an open-loop performance metric using controllability Grammians. The grouping problem can be converted into a graph partitioning problem which admits a solution via linear matrix inequality (LMI) optimization techniques. Method two is based on closed-loop optimal control performance for saturating control systems. In this case, we find that grouping the actuators allows online control design to account for control saturation. It was determined that the grouping problem is insensitive to changes in actuation authority.

Considers the problem of resolving conflicts involving multiple aircraft. First a framework is formulated where conflicts may be solved efficiently. Within this framework, the conflict resolution problem is shown to be a non-convex, quadratically constrained quadratic program. Cheap lower bounds to this problem are developed based on positive semidefinite relaxations of the dual of this program. A unique method is proposed to systematically determine the regions of the state-space where the conflict resolution algorithm is guaranteed to perform well within the proposed framework.

Under the concept of free flight, aircraft will be allowed much greater flexibility in trajectory planning than ever before. The ability to anticipate and resolve conflicts provides one of the greatest challenges to this proposed environment. In this paper, the following problem is addressed: given two aircraft, their intended trajectories and uncertainty about their behavior, what is their worst-case miss distance over a given time horizon? This question is answered using linear matrix inequalities and positive semi-definite programming. The proposed approach provides guaranteed lower bounds on minimum miss distances in polynomial time. Several increasingly complex examples are given that illustrate the efficiency of the proposed method.

The currently proposed techniques to perform frequency-domain stability analysis against real parametric variations fail, because "discontinuities" of the real stability margin prevent straightforward frequency gridding techniques to work properly. In this paper, we present new robustness indicators that consistently detect these discontinuities.

This paper presents a new approach to fuel-optimal path planning of multiple vehicles using a combination of linear and integer programming. The basic problem formulation is to have the vehicles move from an initial dynamic state to a final state without colliding with each other, while at the same time avoiding other stationary and moving obstacles. It is shown that this problem can be rewritten as a linear program with mixed integer/linear constraints that account for the collision avoidance. A key benefit of this approach is that the path optimization can be readily solved using the CPLEX optimization software with an AMPL/Matlab interface. An example is worked out to show that the framework of mixed integer/linear programming is well suited for path planning and collision avoidance problems. Implementation issues are also considered. In particular, we compare receding horizon strategies with fixed arrival time approaches.

While system identification has traditionally concentrated on identifying systems driven by explicit ordinary differential equations, the recent explosion in computational power has made feasible systems whose dynamics are partly driven by real-time optimization processes. Identification algorithms which could pinpoint the optimization parameters used to drive these closed-loop control systems would clearly find application to receding horizon controllers and other control processes which incorporate online optimization. This work describes a procedure which identifies the optimization parameters at work in many types of receding horizon controllers. If all the control and state constraints are known, then the problem may be recast as identification of objective parameters of a real-time, static optimization problem. Using the necessary conditions of optimality in some cases of interest, this problem is shown to be equivalent to solving a feasibility semi-definite program. In alternate setups, the necessary conditions of optimality lead to a formulation of the identification problem as a feasibility linear or integer program.

Nonconvex quadratic optimization problems and the methods for their analysis have been on the center stage of information and decision systems for the past 50 years. Although most of these problems are very complex in general, all of them may be relaxed to semidefinite programs. In many cases, this relaxation is tight or it may be bounded. The solution to those programs facilitates the solution to the original nonconvex problem, notably via efficient randomization techniques. Engineering applications of nonconvex quadratic programming and related solution techniques are virtually infinite. Examples extracted from the current literature on information and decision systems are provided. These examples include network optimization problems, linear and nonlinear control problems and important linear algebra problems.

This paper considers a multiple conflict resolution problem for air traffic control systems. The time required to optimally solve aircraft conflicts is known to grow exponentially with the number of aircraft involved and may become prohibitive when large numbers of aircraft are involved. As an attempt to circumvent this issue, a heuristic polynomial-time conflict resolution algorithm is proposed on the basis of analysis results on the relationship between primal and dual quadratic programs.

This paper presents a new method for designing full order, dynamic LTI controllers that provide guaranteed levels of H/sub 2/ performance for systems with static, real, parametric uncertainties. The controllers are designed using a D-K iteration, i.e., by iterating between solutions of controller synthesis problem and a performance analysis problem. The controllers are synthesized by solving a set of coupled Riccati equations using a recently proposed iterative technique. Performance analysis is studied using a gradient optimization technique. In order to increase the utility of the method, the analysis and synthesis routines intentionally avoid the use of convex optimization routines, such as LMI solution codes. The design methodology is demonstrated on a realistic structural control problem, a model of the Middeck Active Control Experiment (MACE).

We propose an alternative to gain scheduling for stabilizing a class of nonlinear systems. The computation times required to find stability regions for a given control Lyapunov function vary polynomially with the state dimension for a fixed number of scheduling variables. Control Lyapunov functions to various trim points are used to expand the stability region, and a Lyapunov based synthesis formula yields a control law guaranteeing stability over this region. Robustness to bounded disturbances is easily handled, and the optimal stability margin, defined as a Lyapunov derivative, is recovered asymptotically. We apply the procedure to an example.

Most existing subspace identification algorithms assume that a single input to output data set is available. Motivated by a real life problem on the F18-SRA experimental aircraft, we show how these algorithms are readily adapted to handle multiple data sets. We show by means of an example the relevance of such an improvement.