Robot reachability problem: A nonlinear optimization approach

The reachability of a robot manipulator to a target is defined as its ability to move its joints and links in free space in order for its hand to reach the given target. This paper presents a way of testing the reachability of a robot to given target. The target could be a three dimensional object represented by a cuboid, a line or merely a point.The reachability test problem is transformed into a nonlinear optimization problem, which is solved by using the Tunneling Algorithm [1–3].The paradigm of the Tunneling Algorithm is described in detail. Several examples of testing the reachability of two robots to given targets are presented and the results are compared with that of the existing RGRG algorithm [5]. The results of comparisons show that the Tunneling Algorithm is better than the RGRG algorithm. It can always obtain the correct answers of testing, and it is effective and suitable to solve the reachability test problem.This project is partially supported by a grant from Martin Marietta (ORNL) 19x-55902V. Also this project is partially funded by ONR grant N00014-94-1-0343.     

On one problem of construction of energy-saving schedules

Construction of energy-saving schedules for the execution of n jobs on a processor with the use of the dynamic voltage scaling (DVS) mechanism is considered. A formal problem statement is presented. The problem is shown to be NP-hard. An algorithm with complexity O(n ₂/ε) guaranteeing finding of a (1 + ε)-approximate solution is suggested.     

On one boundary problem for nonlinear stationary controlled system

The object of study is nonlinear stationary controlled system of ordinary differential equations with constant disturbance in the right part. The problem of constructing the synthesising control function providing the transfer of this system from the initial state to the origin is considered. The sufficiently simple for numerical implementation algorithm of solution of the above-mentioned problem is obtained. It is shown that for local null controllability of the considered system, it is sufficient that the conditions of the Kalman's type were satisfied. In addition, the estimates restricting the choice of initial conditions and external disturbances under which the transfer is guaranteed are obtained. The main idea of the method of construction of the desired control function consists in reducing the original problem to stabilisation of a special kind linear non-stationary system and solving the Cauchy problem for an auxiliary system of ordinary differential equations closed by stabilising control. The simplicity of the realisation of this algorithm is determined by the construction of the auxiliary system and its stabilisation that could be obtained by analytical methods. The effectiveness of the method is illustrated by solving the problem of crane control and its numerical simulation.     

On the optimal reachability problem of weighted timed automata

We study the cost-optimal reachability problem for weighted timed automata such that positive and negative costs are allowed on edges and locations. By optimality, we mean an infimum cost as well as a supremum cost. We show that this problem is PSpace-Complete. Our proof uses techniques of linear programming, and thus exploits an important property of optimal runs: their time-transitions use a time τ which is arbitrarily close to an integer. We then propose an extension of the region graph, the weighted discrete graph, whose structure gives light on the way to solve the cost-optimal reachability problem. We also give an application of the cost-optimal reachability problem in the context of timed games. Research supported by the FRFC project “Centre Fédéré en Vérification” funded by the Belgian National Science Foundation (FNRS) under grant nr 2.4530.02.     

On the reachability problem for 5-dimensional vector addition systems

The reachability sets for vector addition systems of dimension less than or equal to five are shown to be effectively computable semilinear sets. Thus reachability, equivalence and containment are decidable up to dimension 5. An example of a non-semilinear reachability set is given for dimension 6.     

On a reachability problem for affine hypersurface systems on polytopes

This paper studies the problem for an affine hypersurface system (with n−1 inputs) to reach a polytopic target set starting from inside a polytope in the state space. We present a solution which begins with a characterization of solvability by open-loop control and concludes with a procedure to synthesize a feedback control. Our emphasis is on methods of subdivision, triangulation, and covers which explicitly account for the capabilities of the control system. In contrast with the previous literature, the partition methods are guaranteed to yield a correct feedback synthesis, assuming the problem is solvable by open-loop control.     

On one variational Butkovskii problem

One of the unsolved problems of the theory of optimal control, the Butkovskii variational problem which is of importance for applications, was solved.     

External estimates of the reachability sets of nonlinear controlled systems

Consideration was given to formation of the external estimates of the reachability sets of the nonlinear controlled systems in the form of the level sets of the functions satisfying the differential Hamilton-Jacobi inequalities. The trajectories of the nonlinear system are estimated by modifying the estimates of its linear part. The constructions proposed are based on comparing the systems of differential inequalities. Applications of the reachability sets of the multivariable controlled systems with nonlinear cross connections to the ellipsoidal estimates were examined.     

On one problem of integer optimization

A recognition problem of the following form is studied: to find put for the prescribed polyhedron whether the maximum of the linear objective function is achieved at its integral point. It is established that this problem is NP-hard in the general case and polynomially solvable in the class of rooted semimetric polyhedra.     

On the reachability of quantized control systems

In this paper, we study control systems whose input sets are quantized, i.e., finite or regularly distributed on a mesh. We specifically focus on problems relating to the structure of the reachable set of such systems, which may turn out to be either dense or discrete. We report results on the reachable set of linear quantized systems, and on a particular but interesting class of nonlinear systems, i.e., nonholonomic chained-form systems. For such systems, we provide a complete characterization of the reachable set, and, in case the set is discrete, a computable method to completely and succinctly describe its structure. Implications and open problems in the analysis and synthesis of quantized control systems are addressed     

Two algorithms for a reachability problem in one-dimensional space

Two algorithms are proposed to solve a reachability problem among time-dependent obstacles in 1D space. In the first approach, the motion planning problem is reduced to a path existence problem in a directed graph. The algorithm is very simple, with running time O(n²), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log₂ n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist     

On a nonlinear multivariable servomechanism problem

Multivariable nonlinear plants with both measured and unmeasured vector disturbance signals are considered. Output-feedback, dynamic control laws are designed for the problem of tracking a constant or slowly-varying reference input while rejecting constant or slowly-varying disturbances.     

On one method of solving the partial covering problem

We propose and analyze a method for exact solution of the partial covering problem, which has numerous applications. Results of a numerical experiment indicate that the method is efficient.Translated from Kibernetika, No. 1, pp. 96–98, January–February, 1989.     

On reachability graphs of Petri nets

Petri net is a powerful tool for system analysis and design. Several techniques have been developed for the analysis of Petri nets, such as reachability trees, matrix equations and reachability graphs. This article presents a novel approach to constructing a reachability graph, and discusses the application of the reachability graph to Petri nets analysis.     

On the reachability set of automaton counter machines

Properties of automaton counter machines are considered. The set of reachability states of any automaton one-counter machine is proved to be a semilinear set. An algorithm for constructing this set is described. In addition, the reachability sets of any reversal-bounded automaton counter machine and any flat automaton counter machine are also semilinear.     

On the span reachability of polynomial state-affine systems

The purpose of this report is to derive an explicit condition for the span reachability of a discrete polynomial state-affine system described byx(k+1)=(A_{0} +Sigmamin{i=1}max{r}u^{i}(k)A_{i})x(k)+ summin{i=1}max{r} u^{i}(k)B_{i}, (k=0,1,...)(1) whereris a positive integer,x in R^{n}, u in R^{1},u^{i}denotes the ith power ofu, and Aiand Biare matrices of appropriate dimensions. In order to define input sequences which can construct reachable state vectors from the origin to span the whole state space, a generalized type of the Vandermonde's matrix is newly defined and utilized fully. Although the algebraic structure of (1) is more complicated than discrete bilinear systems, the result turns out to be quite analogous to each other.     

Some decision problems related to the reachability problem for Petri nets

In this paper, we show that (1) the question to decide whether a given Petri net is consistent, M_o-reversible or live is reduced to the reachability problem in a unified manner, (2) the reachability problem for Petri nets is equivalent to the equality problem and the inclusion problem for the sets of all firing sequences of two Petri nets, (3) the equality problem for the sets of firing sequences of two Petri nets with only two unbounded places under homomorphism is undecidable, (4) the coverability and reachability problems are undecidable for generalized Petri nets in which a distinguished transition has priority over the other transitions, and (5) the reachability problem is undecidable for generalized Petri nets in which some transitions can reset a certain place to zero marking.     

On the “soft” capture in one group pursuit problem

For the generalized L.S. Pontryagin example, sufficient conditions for a “soft” capture of one evader by a group of pursuers are obtained.