CBUG: A Quadratically Competitive Mobile Robot Navigation Algorithm

This paper is concerned with online navigation of a size $D$ mobile robot in an unknown planar environment. A formal means for assessing algorithms for online tasks is competitiveness. For the navigation task, competitiveness measures the algorithm's path length relative to the optimal offline path length. While competitiveness usually means constant relative performance, it is measured in this paper in terms of a quadratic relationship between online performance and optimal offline solution. An online navigation algorithm for a size D robot called CBUG is described. The competitiveness of CBUG is analyzed and shown to be quadratic in the length of the shortest offline path. Moreover, it is shown that, in general, quadratic competitiveness is the best achievable performance over all online navigation algorithms. Thus, up to constants, CBUG achieves optimal competitiveness. The algorithm is improved with some practical speedups, and the usefulness of its competitiveness in terms of path stability is illustrated in office-like environments.      

Stability of nonlinear time-varying feedback systems

In this paper, the stability of nonlinear time-varying feedback systems is studied using a “passive operator” technique. The feedback system is assumed to consist of a linear time-invariant operator G(s) in the forward path and a nonlinear time-varying gain function f(·)K(t) in the feedback path. The stability condition indicates that the bound on the time derivative [dK(t)/(dt)] depends both on the nonlinearity f(·) and the multiplier Z(s) chosen to make G(s)Z(s) positive real. It is also shown that the main result in this paper can be specialized to yield many of the results obtained so far for nonlinear time-invariant systems and linear time-varying systems.     

未知环境下移动机器人安全路径规划的一种神经网络方法

针对未知环境下移动机器人的安全路径规划,采用了一种局部连接Hopfield神经网 络(Hopfield Neural Networks,HNN)规划器;分析了HNN稳定性,并给出了存在可行路 径的条件.如果存在可行路径,该方法不存在非期望的局部吸引点,并在连接权设计中兼顾 "过近"和"过远"来形成安全路径.为在单处理器上有效地在线路径规划,采用多顺序的 Gauss-Seidel迭代方法来加速HNN势场的传播.结果表明该方法具有较高的实时性和环境 适应性.     

适用于路径跟踪控制的自适应MPC算法研究

为提高自动驾驶车辆在不同工况下的路径跟踪精度和行驶稳定性,基于车辆的单轨模型和模型预测控制（MPC）理论,提出一种依据跟踪偏差和道路曲率自适应调整成本函数权重系数的路径跟踪控制算法。该算法主要是通过模糊控制理论动态优化传统MPC路径跟踪控制器中权重系数矩阵,使得当车辆与参考路径偏差比较大时,能够快速减小跟踪偏差,保证车辆行驶的安全性;当路径跟踪偏差比较小,且参考路径曲率比较小时,使得系统更加侧重行驶稳定性的要求。为验证所设计的路径跟踪控制器的性能,搭建CarSim/Simulink联合仿真模型,在联合仿真过程中,基于权重系数自适应的MPC路径跟踪控制器与基于权重系数为常量的MPC路径跟踪控制器相比,路径跟踪精度和车辆的行驶稳定性均得到了提高。     

Stochastic stability properties of jump linear systems

Jump linear systems are defined as a family of linear systems with randomly jumping parameters (usually governed by a Markov jump process) and are used to model systems subject to failures or changes in structure. The authors study stochastic stability properties in jump linear systems and the relationship among various moment and sample path stability properties. It is shown that all second moment stability properties are equivalent and are sufficient for almost sure sample path stability, and a testable necessary and sufficient condition for second moment stability is derived. The Lyapunov exponent method for the study of almost sure sample stability is discussed, and a theorem which characterizes the Lyapunov exponents of jump linear systems is presented. Finally, for one-dimensional jump linear system, it is proved that the region for δ-moment stability is monotonically converging to the region for almost sure stability at δ↓0⁺     

水质油污染原位传感器稳定性设计

由于受光源不稳、环境光干扰、标准曲线非线性及沾污的影响,传感器的稳定性表现不佳.为此,基于紫外荧光测量原理,分别从结构、工艺及算法3个方面做了优化设计.光路设计中引入了参比检测,ZEMAX软件仿真结果显示"十"字光路可行.聚四氟乙烯、光学镀膜的采用及电刷设计可有效防止油污粘附及生物附着.遮光罩为传感器营造一个检测暗腔,有效解决了环境光干扰问题.实验表明:传感器测量样品时,荧光信号的变异系数<0.3%.以浓度30 μg/L为例,模拟光强衰减时荧光信号的变异系数为1.28%.样品浓度为62.4 μg/L时,扩展不确定度为0.256 μg/L(k=2).传感器的稳定性设计取得了较理想的成果,但距离实际应用还有差距,主要是浊度、温度等影响因子未引入到算法修正模型中.     

On tracking control of a class of complementary-slackness hybrid mechanical systems

In this note we consider the problem of feedback control of n-dof (degree-of-freedom) rigid manipulators subject to a scalar frictionless unilateral constraint is the vector of generalized coordinates). The stability analysis relies on a stability concept that incorporates the hybrid and nonsmooth dynamical feature of the overall system. It is shown that stability of the closed-loop system can be obtained. This work generalizes the results in [Brogliato et al. (IEEE Trans. Automat. Control 42(2) (1997) 200–215)] which were mainly restricted to the 1-dof case. It also clarifies some concepts related to the hybrid nature of closed-loop complementary-slackness mechanical systems.     

Ct coverage — initial results

Software testing techniques based upon automated analysis of control flow are useful for improving software reliability. The fundamental types of control flow analysis, in ascending order of effectiveness, are statement, branch, and path coverage. Automated tools that perform branch coverage analysis are now accepted practice and researchers are exploring the area that exists between branch and path analysis. Path testing is complicated by the huge number of paths in ordinary programs and by anomalies, such as infeasible paths. The Ct testing strategy is a method for obtaining a manageable set of path classes by specifying a minimum iteration count k. The Ct test coverage metric is a measurement of the proportion of Ct path classes that are exercised within a program. This paper describes an initial experiment in which a special, automated tool was used to evaluate the Ct coverage of tests for a C program of significant size. The results of the study showed that high values of branch coverage may not necessarily imply high path coverage, that approximately 15% of the functions analysed were too complex to analyse effectively, and that the majority of the remaining functions achieved on the order of 11% Ct k=1 coverage. Experimental work in the attainment of high Ct coverage suggests the development of a new, more efficient software testing strategy, which combines Ct path and data flow analysis.     

Optimal Collision Free Path Planning for Non-Synchronized Motions

This paper treats the path finding problem for robots whose joints cannot be controlled in such a way that the end-effector follows a prespecified trajectory. Hence, if two or more joints are moving at the same time during the motion, the relative positions for the joints, i.e. the exact positions of the end-effector, are not known. This may be due to the low level control of the robot (for example, with heavy load robots), or due to a complicated kinematic structure. For such mechanisms a motion is specified by certain intermediate positions (values for all joints) along a desired path. These intermediate positions (synchronization points) and the requirement that the motions in the single joints are monotonous between consecutive synchronization points guarantee a certain structure of a path. We develop a new algorithm that determines paths for such mechanisms, i.e., a respective sequence of intermediate positions, such that the path is collision free and is shortest with respect to different optimality criteria.     

移动自组网中基于路径稳定性的QoS路由协议

随着多媒体应用日益普及，在移动自组网中提供QoS已经逐渐成为自组网研究的热点问题，然而现有的自组网QoS路由协议主要集中研究如何找到满足QoS条件的可行路径而没有考虑可行路径的稳定性，针对移动自组网的特点，提出了基于路径稳定性的QoS路由协议PSQRP，该协议基于路径稳定性PSF来选择路由，减少了链路断开的概率，同时协议采用了主次预约技术来预约网络资源，进一步提高了协议的请求成功率，模拟结果表明，在动态的网络环境下，PSQRP协议能够取得良好的性能。     

Traversal of an Unknown Directed Graph by a Finite Robot

A covering path in a directed graph is a path passing through all vertices and arcs of the graph, with each arc being traversed only in the direction of its orientation. A covering path exists for any initial vertex only if the graph is strongly connected, i.e., any of its vertices can be reached from any other vertex by some path. The strong connectivity is the only restriction on the considered class of graphs. As is known, on the class of such graphs, the covering path length is (nm), where n is the number of vertices and m is the number of arcs. For any graph, there exists a covering path of length O(nm), and there exist graphs with covering paths of the minimum length (nm). The traversal of an unknown graph implies that the topology of the graph is not a priori known, and we learn it only in the course of traversing the graph. At each vertex, one can see which arcs originate from the vertex, but one can learn to which vertex a given arc leads only after traversing this arc. This is similar to the problem of traversing a maze by a robot in the case where the plan of the maze is not available. If the robot is a general-purpose computer without any limitations on the number of its states, then traversal algorithms with the same estimate O(nm) are known. If the number of states is bounded, then this robot is a finite automaton. Such a robot is an analogue of the Turing machine, where the tape is replaced by a graph and the cells are assigned to the graph vertices and arcs. Currently, the lower estimate of the length of the traversal by a finite robot is not known. In 1971, the author of this paper suggested a robot with the traversal length O(nm + n ²logn). The algorithm of the robot is based on the construction of the output directed spanning tree of the graph and on the breadth-first search (BFS) on this tree. In 1993, Afek and Gafni [1] suggested an algorithm with the same estimate of the covering path length, which was also based on constructing a spanning tree but used the depth-first search (DFS) method. In this paper, an algorithm is suggested that combines the breadth-first search with the backtracking (suggested by Afek and Gafni), which made it possible to reach the estimate O(nm + n ²loglogn). The robot uses a constant number of memory bits for each vertex and arc of the graph.     

Management information and its optimal allocation for ATM networks with a protection mechanism

This paper focuses on the definition and allocation of management information for ATM broadband networks that adopt the virtual path protection mechanism. The definition of management information is proposed to represent, in accordance with international standards, a virtual path with the protection mechanism. To achieve accurate representation, the proposed method features the two distinct managed object classes derived from the trail concept, which has been specified in ITU-TS recommendations. The allocation of management information is optimized by using computer simulations. The criterion for the optimization is the rapidity of tracking the change-over/back and setting up a virtual path. The system that exchanges messages and updates management information is modeled as a queueing system to evaluate the rapidity. Several alternative allocation methods are compared, and the best method is determined.     

Real-time Collision-free Path Planning of Robot Manipulators using Neural Network Approaches

In this paper, a novel neural network approach to real-time collision-free path planning of robot manipulators in a nonstationary environment is proposed, which is based on a biologically inspired neural network model for dynamic trajectory generation of a point mobile robot. The state space of the proposed neural network is the joint space of the robot manipulators, where the dynamics of each neuron is characterized by a shunting equation or an additive equation. The real-time robot path is planned through the varying neural activity landscape that represents the dynamic environment. The proposed model for robot path planning with safety consideration is capable of planning a real-time comfortable path without suffering from the too close nor too far problems. The model algorithm is computationally efficient. The computational complexity is linearly dependent on the neural network size. The effectiveness and efficiency are demonstrated through simulation studies.     

New Approximation Results for the Maximum Scatter TSP

We consider the following maximum scatter traveling salesperson problem (TSP): given an edge-weighted complete graph ${\cal G}=(S,E)$, find a Hamiltonian path or cycle such that the length of a shortest edge is maximized. In other words, the goal is to have each point far away (most scattered) from the points that are visited just before or just after it in the path/cycle. This is also referred to as the max-min 1-neighbor TSP. More generally, in the max-min m-neighbor TSP problem, the goal is to maximize the minimum distance between any point and all of its m-neighbors along the path/cycle. An m-neighbor of p is a point that is at most m points away from p in the path/cycle. These problems are closely related to the bottleneck TSP, and are motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper we give O(n^2.5)-time approximation algorithms for the max-min 2-neighbor TSP with the triangle inequality. We achieve an approximation factor of 12 for the path version, and a factor of 18 for the cycle version of the problem, improving the previous best factors of 32 and 64, respectively, for all cases of n. Moreover, we present an O(mn^2.5)-time algorithm that achieves a constant approximation factor of 16 for the path version of the max-min m-neighbor TSP with the triangle inequality when n = (m+1)k or when n = (m + 1)k + m, where $m \in (2,n)$ is part of the input. This significantly improves the previous best approximation factor of $4\cdot 8^{\lceil m/2 \rceil}$, from exponential in m to a small constant.     

On the good use of the spectral radius of a matrix

In a recent correspondence [1], attention was called to the "misuse" of spectral radius of system matrices in stability, analysis. An assertion made in [1] is elaborated on more precisely in this note. In addition, we present some interesting stability results for "slowly varying" linear systems, highlighting the crucial role played by the spectral radius in convergence analysis.     

Coverage of Known Spaces: The Boustrophedon Cellular Decomposition

Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applications include de-mining, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cellular decomposition approach, for the purposes of coverage. Essentially, the boustrophedon decomposition is a generalization of the trapezoidal decomposition that could allow for non-polygonalobstacles, but also has the side effect of having more efficient coverage paths than the trapezoidal decomposition. Each cell in the boustrophedon decomposition is covered with simple back and forth motions. Once each cell is covered, then the entire environment is covered. Therefore, coverage is reduced to finding an exhaustive path through a graph which represents the adjacency relationships of the cells in the boustrophedon decomposition. This approach is provably complete and experiments on a mobile robot validate this approach.     

A note on path bipancyclicity of hypercubes

In [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97], the authors showed that any path in an n-cube with length of k, 2k2n−4, lies on a cycle of every even length from 2k to 2ⁿ inclusive. Base on Lemma 5 of that paper, they proved the subcase 2.2.1 of the main theorem of that paper. However, the lemma is false, therefore, we propose a lemma to replace that lemma. Therefore, the main result of [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97] is still correct.     

On mapping processes to processors in distributed systems

This paper is concerned with the implementation of parallel programs on networks of processors. In particular, we study the use of the network augmenting approach as an implementation tool. According to this approach, the capabilities of a given network of processors can be increased by adding some auxiliary links among the processors. We prove that the minimum set of edges needed to augment a line-like network so that it can accommodate a parallel program is determined by an optimal path cover of the graph representation of the program. Anoptimal path cover of a simple graphG is a set of vertex-disjoint paths that cover all the vertices ofG and has the maximum possible number of edges. We present a linear time optimal path covering algorithm for a class of sparse graphs. This algorithm is of special interest since the optimal path covering problem is NP-complete for general graphs. Our results suggest that a cover and augment scheme can be used for optimal implementation of parallel programs in line-like networks.A preliminary version of this paper was presented at the 6th IEEE Conference on Computer Communications (INFOCOM '87).This reseach is supported in part by National Semiconductor (Israel), Ltd.