Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape

The problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton's tactile sensor. This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper bounds on the length of generated paths are produced.Supported in part by the National Science Foundation Grant DMC-8519542.     

Dynamic path planning for a mobile automaton with limited information on the environment

The problem of path planning is studied for the case of a mobile robot moving in an environment filled with obstacles whose shape and positions are not known. Under the accepted model, the automaton knows its own and the target coordinates, and has a "sensory" feedback which provides it with local information on its immediate surroundings. Ibis information is shown to be sufficient to guarantee reaching a global objective (the target), while generating reasonable (if not optimal) paths. A lower bound on the length of paths generated by any algorithm operating with uncertainty is formulated, and two nonheuristic path planning algorithms are described. In the algorithms, motion planning is done continuously (dynamically), based on the automaton's current position and on its feedback. The effect of additional sources of information (e.g., from a vision sensor) on the outlined approach is discussed.     

Comments on `Dynamic path planning for a mobile automation withlimited information on the environment' [with reply]

Two path-planning algorithms are presented for the case of an uncertain environment, and a bound for the length of path generated by each algorithm is given. Lucas shows that the least upper bound corresponding to the first algorithm is incorrect, and suggests a revised algorithm which has that upper bound for its generated path lengths. However, Lumelsky et al. points out that the modification by Lucas, which requires the automaton to try to stick to the M-line, would defect the main idea behind the algorithm and thus cannot be accepted     

Linear-time border-tracing algorithms for quadtrees

In applications where the quadtree is used as an underlying object representation, a number of basic operations are implemented as a trace along the border of the object's region. A technique is presented that determines a way to shift any given scene (as well as its quadtree), so that the border of all the objects in the scene can be traversed in time proportional to the length of all the borders in the scene (or the number of blocks when the scene is represented as a quadtree). This determination is shown to be performed in time proportional to the length of all the borders in the scene. This allows the direct translation of a number of chain-code algorithms into quadtree algorithms without loss of asymptotic worst-case efficiency. This results in improved worst-case analyses of algorithms that convert chain codes into quadtrees and that perform connected component labeling of images represented as quadtrees.     

Linear-time border-tracing algorithms for quadtrees

In applications where the quadtree is used as an underlying object representation, a number of basic operations are implemented as a trace along the border of the object's region. A technique is presented that determines a way to shift any given scene (as well as its quadtree), so that the border of all the objects in the scene can be traversed in time proportional to the length of all the borders in the scene (or the number of blocks when the scene is represented as a quadtree). This determination is shown to be performed in time proportional to the length of all the borders in the scene. This allows the direct translation of a number of chain-code algorithms into quadtree algorithms without loss of asymptotic worst-case efficiency. This results in improved worst-case analyses of algorithms that convert chain codes into quadtrees and that perform connected component labeling of images represented as quadtrees.The support of the National Science Foundation under Grant IRI-88-02457 is gratefully acknowledged.     

The complexity of restricted regular expressions and the synthesis problem for finite automata

It is known that for every restricted regular expression of length n there exists a nondeterministic finite automaton with n + 1 states giving rise to the upper bound of 2ⁿ + 1 on the number of states of the corresponding reduced automaton. In this note we show that this bound can be attained for all n ? 2, i.e., the upper bound 2ⁿ + 1 is optimal. An observation is then made about the synthesis problem for nondeterministic finite automata.     

Dynamic path planning for a planar articulated robot arm moving amidst unknown obstacles

This work is concerned with planning collision-free paths for a robot arm moving in an environment filled with unknown obstacles, where any point of the robot body is subject to collision. To compensate for the uncertainty, the system is provided with sensory feedback information about its immediate surroundings. In such a setting, which presents significant practical and theoretical interest, human intuition is of little help, and designing algorithms with proven convergence thus becomes an important task. We show that, given the target position, local feedback information is sufficient to guarantee reaching a global objective (the target position) and present a nonheuristic algorithm which generates reasonable—if, in general, not optimal—collision-free paths. In this approach, the path is being planned continuously (dynamically), based on the arm's current position and on the sensory feedback. Here, a case of a planar arm with two revolute joints is studied. No constraints on the shape of the robot links or the obstacles are imposed. The general idea is to reduce the problem of motion planning to an analysis of simple closed curves on the surface of an appropriate two-dimensional manifold.     

Shortest synchronizing strings for Huffman codes

Most complete binary prefix codes have a synchronizing string, that is a string that resynchronizes the decoder regardless of its previous state. This work presents an upper bound on the length of the shortest synchronizing string for such codes. Two classes of codes with a long shortest synchronizing string are presented. It is known that finding a synchronizing string for a code is equivalent to finding a synchronizing string of some finite automaton. The Černý conjecture for this class of automata is discussed.     

Towards an Efficient Path-Oriented Tool for Bounded Reachability Analysis of Linear Hybrid Systems using Linear Programming

The existing techniques for reachability analysis of linear hybrid automata do not scale well to problem sizes of practical interest. Instead of developing a tool to perform reachability check on all the paths of a linear hybrid automaton, a complementary approach is to develop an efficient path-oriented tool to check one path at a time where the length of the path being checked can be made very large and the size of the automaton can be made large enough to handle problems of practical interest. This approach of symbolic execution of paths can be used by design engineers to check important paths and thereby, increase the faith in the correctness of the system. Unlike simple testing, each path in our framework represents a dense set of possible trajectories of the system being analyzed. In this paper, we develop the linear programming based techniques towards an efficient path-oriented tool for the bounded reachability analysis of linear hybrid systems.     

String execution time for finite languages: Max is easy, min is hard

In performance evaluation or supervisory control, we often encounter problems of determining the maximum or minimum string execution time for a finite language when estimating the worst-case or best-case performance. It has been shown in the literature that the time complexity for computing the maximum string execution time for a finite language is polynomial with respect to the size of an automaton recognizer of that language and the dimension of the corresponding resource matrices. In this paper we provide a more efficient algorithm to compute such maximum string execution time. Then we show that it is NP-complete to determine the minimum string execution time.     

结合最短路径改进的社会力人群疏散仿真模型

社会力模型广泛应用于人群疏散仿真,针对该模型在仿真过程中存在行人停滞不前、无法通过非凸边形障碍物和疏散路径与行人实际选择的路径不相符等问题,提出了一种社会力改进模型。该模型基于场景中的障碍物生成路径节点,利用这些节点生成无向图,同时考虑了节点的安全系数和拥挤系数对节点通行性的影响生成最短疏散路径。通过改进后的社会力模型进行了多种场景的仿真实验,实验结果显示行人在复杂障碍物场景中能有效绕过障碍物,生成合理的疏散路径,表明该模型有效改善社会力模型,使人群疏散仿真更加真实。     

Objective estimation of pain based on facial expression,vital signs and body movements

An intelligent automaton should always arrive at its goal automatically while avoiding the obstacles in a two-dimensional (2D) world. If the automaton does not know the shape or location of any obstacle in the world, it gathers information on its neighbourhood from some sensor, and according to the sensor information, it avoids the closer obstacles. In this situation, a sensor-based path-planning algorithm is used to determine the automaton's action flexibly according to changes in the sensor information. By this method, the automaton usually avoids the closer obstacles on the basis of the local information but it may circulate around some of the obstacles in the world because of the locality of the sensor information. If deadlock occurs, the automaton does not arrive at the goal at all. To overcome this drawback, we address a sufficient condition for designing a family of deadlock-free sensor-based path-planning algorithms in an uncertain world. Within this family, the automaton basically goes straight to the goal. If the automaton occasionally finds a hit point against an unfamiliar obstacle via the touch sensor, it traces the obstacle by touch and in time it finds a way to go straight to the goal again around the obstacle. Even under those conditions the automaton continues to trace the obstacle until its Euclidean distance to the goal is smaller than a distance index which is decreasing asymptotically. This is the sufficient condition, under which the automaton leaves the obstacle to go straight to the goal. This asymptotical approach of the leave point to the goal guarantees that the algorithm family will be deadlock-free. In the family, the automaton always goes straight to the goal if it does not trace any obstacle in the world. Thus, if the leave point comes asymptotically close to the goal, the circular space where the automaton can hit some obstacle in future decreases asymptotically. Therefore the circular space finally goes out of existence and consequently the automaton arrives at the goal. As a result, the family ensures the convergence of the automaton to the goal in an uncertain 2D world.     

An articulated limb motion planner for optimized movement

Task level animation of articulated figures, such as the human body, requires the ability to generate collision-free goal-directed motion of individual limbs in the presence of obstacles. This paper describes a new articulated limb motion planner for goal-directed point-to-point reaching motions. The produced motion avoids obstacles while optimizing an objective function. This two-phase algorithm uses heuristic guided Monte Carlo techniques to create a consistent underlying paradigm. The first phase consists of an existing potential field based random path planner which generates a population of candidate paths. This initial population is fed into the second phase, a genetic algorithm, which iteratively refines the population as it optimizes with respect to the objective function. The refinement process works on the principle of path coherency, the idea that a family of closely related collision-free paths lies in the vicinity of a given collision-free path. This paper focuses on seven different optimization functions. Optimized trajectories produced by the new motion planner are compared to those generated solely by the random path planner. The presented algorithm is flexible in that a wide range of objective functions can be optimized. Applications of the algorithm include task level animation, ergonomics and robotics.     

Fooling a two-way nondeterministic multihead automaton with reversal number restriction

Summary We define a language L and show that it can be recognized by no two-way nondeterministic sensing multihead finite automaton with n ^a reversal bound, where n is the length of input words, and 1/3>a>0 is a real number. Since L is recognized by a two-way deterministic two-head finite automaton working in linear time we obtain, for two-way finite automata, that time, reading heads, and nondeterminism as resources cannot compensate for the reversal number restriction.This work was supported as a part of the SPZV I-1-5/8 grant     

Superiority of exact quantum automata for promise problems

In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automaton operating in realtime mode, whereas the size of the corresponding classical automata grows without bound.     

Three-dimensional optimal path planning for waypoint guidance of an autonomous underwater vehicle

In this paper, optimal three-dimensional paths are generated offline for waypoint guidance of a miniature Autonomous Underwater Vehicle (AUV). Having the starting point, the destination point, and the position and dimension of the obstacles, the AUV is intended to systematically plan an optimal path toward the target. The path is defined as a set of waypoints to be passed by the vehicle. Four criteria are considered for evaluation of an optimal path; they are “total length of path”, “margin of safety”, “smoothness of the planar motion” and “gradient of diving”. A set of Pareto-optimal solutions is found where each solution represents an optimal feasible path that cannot be outrun by any other path considering all four criteria. Then, a proposed three-dimensional guidance system is used for guidance of the AUV through selected optimal paths. This system is inspired from the Line-of-Sight (LOS) guidance strategy; the idea is to select the desired depth, presumed proportional to the horizontal distance of the AUV and the target. To develop this guidance strategy, the dynamic modeling of this novel miniature AUV is also derived. The simulation results show that this guidance system efficiently guides the AUV through the optimal paths.     

巡航导弹参考航迹规划算法研究

为了提高巡航导弹的生存能力和杀伤概率,预先规划参考飞行航迹是一个重要的方法.由程序生成规划用数字地图,根据遗传算法的基本思想,采用改进的编码机制对巡航导弹在威胁已知的模拟数字地图上的飞行航迹进行整体规划,航迹种群随机生成,用加入各种威胁和约束条件影响的适应值函数对个体进行评价,通过选择交叉变芹算了使种群进化,最后所得到适应值最高的航迹个体即可作为导掸的参考飞行航迹.通过编程仿真试验,所得参考航迹可以有效的实现地形跟踪、地形威胁回避.算法由于控制参数的限制,得到的最优路径是次优化的;遗传算法的初始种群及控制参数的确定足改善算法寻优性能的主要因素.     

Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning

Robotic Path planning is one of the most studied problems in the field of robotics. The problem has been solved using numerous statistical, soft computing and other approaches. In this paper we solve the problem of robotic path planning using a combination of A* algorithm and Fuzzy Inference. The A* algorithm does the higher level planning by working on a lower detail map. The algorithm finds the shortest path at the same time generating the result in a finite time. The A* algorithm is used on a probability based map. The lower level planning is done by the Fuzzy Inference System (FIS). The FIS works on the detailed graph where the occurrence of obstacles is precisely known. The FIS generates smoother paths catering to the non-holonomic constraints. The results of A* algorithm serve as a guide for FIS planner. The FIS system was initially generated using heuristic rules. Once this model was ready, the fuzzy parameters were optimized using a Genetic Algorithm. Three sample problems were created and the quality of solutions generated by FIS was used as the fitness function of the GA. The GA tried to optimize the distance from the closest obstacle, total path length and the sharpest turn at any time in the journey of the robot. The resulting FIS was easily able to plan the path of the robot. We tested the algorithm on various complex and simple paths. All paths generated were optimal in terms of path length and smoothness. The robot was easily able to escape a variety of obstacles and reach the goal in an optimal manner.     

Reactive automata

A reactive automaton has extra links whose role is to change the behaviour of the automaton. We show that these links do not increase the expressiveness of finite automata but that they can be used to reduce dramatically their state number both in the deterministic case and the non-deterministic case.Typical examples of regular expressions associated with deterministic automata of exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size for the language.     

Mobile Robot Navigation for Moving Obstacles with Unpredictable Direction Changes,Including Humans

In many service applications, mobile robots need to share their work areas with obstacles. Avoiding moving obstacles with unpredictable direction changes, such as humans, is more challenging than avoiding moving obstacles whose motion can be predicted. Precise information on the future moving directions of humans is unobtainable for use in navigation algorithms. Furthermore, humans should be able to pursue their activities unhindered and without worrying about the robots around them. An enhanced virtual force field-based mobile robot navigation algorithm (termed EVFF) is presented for avoiding moving obstacles with unpredictable direction changes. This algorithm may be used with both holonomic and nonholonomic robots. It incorporates improved virtual force functions and an improved method for selecting the sense of the detour force to better avoid moving obstacles. For several challenging obstacle configurations, the EVFF algorithm is compared with five state-of-the-art navigation algorithms for moving obstacles. The navigation system with the new algorithm generated collision-free paths consistently. Methods for solving local minima conditions are proposed. Experimental results are also presented to further verify the avoidance performance of this algorithm.