Search

This paper describes an approach to the control of continuous systems through the use of symbolic models describing the system behavior only at a finite number of points in the state space. These symbolic models can be seen as abstract representations of the continuous dynamics enabling the use of algorithmic controller design methods. We identify a class of linear control systems for which the loss of information incurred by working with symbolic subsystems can be compensated by feedback. We also show how to transform symbolic controllers designed for a symbolic subsystem mb controllers for the original system. The resulting controllers combine symbolic controller dynamics with continuous feedback control laws and can thus be seen as hybrid systems. Furthermore, if the symbolic controller already accounts for software/hardware requirements, the hybrid controller is guaranteed to enforce the desired specifications by construction thereby reducing the need for formal verification. [ABSTRACT FROM AUTHOR]

The article presents an overview on several studies published within the June 2006 issue of "IEEE Transactions on Automatic Control" in the U.S. The study conducted by Sean B. Andersson and Dimitrios Hristu presents a method for generating sequences of symbolic feedback control laws for mobile robots navigating in unknown environments. Another study conducted by L.C.G.J.M. Habets and colleagues investigates the problem of synthesizing control laws for piecewise-affine hybrid systems on simplices. Furthermore, an approach to self-assembly and self-organization is proposed and investigated based on graph grammars by Eric Klavins and colleagues.

In this paper, we define a class of graph grammars that can be used to model and direct concurrent robotic self-assembly and similar self-organizing processes. We give several detailed examples of the formalism and then focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). In both cases, we characterize the number of concurrent steps required to achieve the assembly. We also show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the self-assembly of robotic parts. [ABSTRACT FROM AUTHOR]

In this paper, we consider the synthesis of control laws for piecewise-affine hybrid systems on simplices. The construction is based on the solution to the control-to-facet problem at the continuous level, and on dynamic programming at the discrete level. The construction is given as an explicit algorithm using only linear algebra and reach-set computations for automata; no numerical integration is required. The method is conservative, in that it may fail to find a control law where one exists, but one cannot hope for a sharp algorithm for control synthesis since reachability for piece- wise-affine hybrid systems is undecidable. [ABSTRACT FROM AUTHOR]

The problem of efficiently steering dynamical systems by generating input plans is considered. Plans are considered which consist of finite-length words constructed on an alphabet of input symbols, which could be, e.g., transmitted through a limited capacity channel to a remote system, where they can be decoded in suitable control actions. Efficiency is considered in terms of the computational complexity of plans, and in terms of their description length (in number of bits). We show that, by suitable choice of the control encoding, finite plans can be efficiently built for a wide class of dynamical systems, computing arbitrarily close approximations of a desired equilibrium in polynomial time. The paper also investigates how the efficiency of planning is affected by the choice of inputs, and provides some results as to optimal performance in terms of accuracy and range. [ABSTRACT FROM AUTHOR]

Combinatorial optimization over continuous and integer variables is a useful tool for solving complex optimal control problems of hybrid dynamical systems formulated in discrete- time. Current approaches are based on mixed-integer linear (or quadratic) programming (MIP), which provides the solution after solving a sequence of relaxed linear (or quadratic) programs. MIP formulations require the translation of the discrete/logic part of the hybrid problem into mixed-integer inequalities. Although this operation can be done automatically, most of the original symbolic structure of the problem (e.g., transition functions of finite state machines, logic constraints, symbolic variables, etc.) is lost during the conversion, with a consequent loss of computational performance. In this paper, we attempt to overcome such a difficulty by combining numerical techniques for solving convex programming problems with symbolic techniques for solving constraint satisfaction problems (CSP). The resulting ‘hybrid’ solver proposed here takes advantage of CSP solvers for dealing with satisfiability of logic constraints very efficiently. We propose a suitable model of the hybrid dynamics and a class of optimal control problems that embrace both symbolic and continuous variables/functions, and that are tailored to the use of the new hybrid solver. The superiority in terms of computational performance with respect to commercial MIP solvers is shown on a centralized supply chain management problem with uncertain forecast demand. [ABSTRACT FROM AUTHOR]

We consider control questions for finite automata viewed as input/output systems. In particular, we find estimates of the minimal number of states of an automaton able to control a given automaton. We prove that, on average, feedback closed-loop control automata do not have fewer states than open-loop control automata when the control objective is to steer the controlled automaton to a target state. We compare our approach to other ways of formalizing of formalizing analogous control objectives. [ABSTRACT FROM AUTHOR]

We discuss the generation of symbolic feedback con- trol sequences for navigating a sparsely-described and uncertain environment, together with the problem of sensing landmarks sufficiently well to make feedback meaningful. We explore the use of a symbolic control approach for mitigating the lack of a detailed map of the environment and for reducing the complexity associated with finding control laws which steer a control system between distant locations. Under our language-based approach, control inputs take the form of symbolic strings. The decision process that generates those strings is guided by estimates of the vehicle's location within a set of important landmarks and by the statistical effectiveness of each string. This arrangement, and in particular the symbolic nature of the control set, allows us to formulate and solve a class of optimal navigation problems which would be exceedingly difficult to handle if approached at the level of sensors and actuators. Our approach is illustrated in a series of numerical indoor navigation experiments. [ABSTRACT FROM AUTHOR]