共查询到20条相似文献,搜索用时 0 毫秒
1.
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. 相似文献
2.
M. A. Trushnikov 《Programming and Computer Software》2010,36(6):337-342
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
2/ε) guaranteeing finding of a (1 + ε)-approximate solution is suggested. 相似文献
3.
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. 相似文献
4.
Patricia Bouyer Thomas Brihaye Véronique Bruyère Jean-François Raskin 《Formal Methods in System Design》2007,31(2):135-175
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. 相似文献
5.
6.
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. 相似文献
7.
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. 相似文献
8.
Yu. V. Egorov 《Automation and Remote Control》2012,73(8):1301-1304
One of the unsolved problems of the theory of optimal control, the Butkovskii variational problem which is of importance for applications, was solved. 相似文献
9.
M. I. Gusev 《Automation and Remote Control》2012,73(3):450-461
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. 相似文献
10.
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. 相似文献
11.
On the reachability of quantized control systems 总被引:1,自引:0,他引:1
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 相似文献
12.
Dajin Wang Sutner K. 《IEEE transactions on systems, man, and cybernetics. Part A, Systems and humans : a publication of the IEEE Systems, Man, and Cybernetics Society》1998,28(4):478-486
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(n2), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log2 n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist 相似文献
13.
On a nonlinear multivariable servomechanism problem 总被引:1,自引:0,他引:1
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. 相似文献
14.
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. 相似文献
15.
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. 相似文献
16.
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. 相似文献
17.
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) wherer is a positive integer,x in R^{n}, u in R^{1},u^{i} denotes the ith power ofu , and Ai and Bi are 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. 相似文献
18.
In this paper, we show that (1) the question to decide whether a given Petri net is consistent, Mo-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. 相似文献
19.
20.
N. N. Petrov I. N. Shuravina 《Journal of Computer and Systems Sciences International》2009,48(4):521-526
For the generalized L.S. Pontryagin example, sufficient conditions for a “soft” capture of one evader by a group of pursuers are obtained. 相似文献