A genetic-fuzzy approach for mobile robot navigation among moving obstacles

In this paper, a genetic-fuzzy approach is developed for solving the motion planning problem of a mobile robot in the presence of moving obstacles. The application of combined soft computing techniques — neural network, fuzzy logic, genetic algorithms, tabu search and others — is becoming increasingly popular among various researchers due to their ability to handle imprecision and uncertainties that are often present in many real-world problems. In this study, genetic algorithms are used for tuning the scaling factors of the state variables (keeping the relative spacing of the membership distributions constant) and rule sets of a fuzzy logic controller (FLC) which a robot uses to navigate among moving obstacles. The use of an FLC makes the approach easier to be used in practice. Although there exist many studies involving classical methods and using FLCs they are either computationally extensive or they do not attempt to find optimal controllers. The proposed genetic-fuzzy approach optimizes the travel time of a robot off-line by simultaneously finding an optimal fuzzy rule base and optimal scaling factors of the state variables. A mobile robot cant then use this optimal FLC on-line to navigate in presence of moving obstacles. The results of this study on a number of problem scenarios show that the proposed genetic-fuzzy approach can produce efficient knowledge base of an FLC for controlling the motion of a robot among moving obstacles.     

Hazard and safety regions for paths with constrained curvature

In this paper the problem of collision analysis for a mobile robot operating in a planar environment with moving objects (obstacles) is addressed. The pattern of motion of the potential obstacles cannot be predicted; only a bound on their maximum velocity is available. Based on this information, at its current position the robot constructs the Hazard Region that corresponds to the path it contemplates. If the Hazard Region contains at least one obstacle, then there is a potential for this obstacle to collide with the robot (in which case perhaps another path should be planned). We first derive the solution for Hazard Region for two standard path primitives, a straight line segment and a circular arc segment; the solution is exact, except for one special case (for which the approximation error is estimated). This result is then applied to a more complex case when the path presents a combination of those primitives. Such are, for example, the optimal (shortest) paths with constrained curvature (known as Dubins paths [3]), which connect two points, each with a prescribed direction of motion. © 1998 B. G. Teubner Stuttgart—John Wiley & Sons, Ltd.     

Pathplanning and control of an autonomous robot vehicle with a manipulator

An autonomous mobile robot is presented. It consists of two parts: a mobile vehicle underneath a robotarm with DOF 5. These two are a nonholomic (the mobile vehicle) and a holonomic subsystem (the robotarm). To give the robot orders or tasks to accomplish this can be done from an external controlsoftware via TCP–IP to the controlsoftware of the robot. An embedded system involves chart creation, pathplanning (global, local), evaluation of sensorsignals, object– and/or marker–detection and a controlled movement. Futhermore it communicates over FIFOs with an nonrealtime–task which allows a communication via TCP–IP. Several sensors are implemented, e.g. infrared–/ ultrasonic–range sensors connected via CAN to the embedded board, as well as the control boards for each engine. A Laserscanner is installed in front of the robot to detect edges and obstacles. For marker–tracking and object recognition an USB–Webcam is added on the robotarm. For avoidance of collisions between the robotarm and the mobile robot a repeller is introduced. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Heuristic fuzzy-neuro network and its application to reactive navigation of a mobile robot

A novel pattern recognition approach to reactive navigation of a mobile robot is presented in this paper. A heuristic fuzzy-neuro network is developed for pattern-mapping between quantized ultrasonic sensory data and velocity commands to the robot. The design goal was to enable an autonomous mobile robot to navigate safely and efficiently to a target position in a previously unknown environment. Useful heuristic rules were combined with the fuzzy Kohonen clustering network (FKCN) to build the desired mapping between perception and motion. This method provides much faster response to unexpected events and is less sensitive to sensor misreading than conventional approaches. It allows continuous, fast motion of the mobile robot without any need to stop for obstacles. The effectiveness of the proposed method is demonstrated in a series of practical tests on our experimental mobile robot.     

Hybrid control for tracking environmental level sets by nonholonomic robots in maze-like environments

A non-holonomic constant-speed robot travels in an unknown maze-like environment cluttered with complex obstacles. Through the obstacle-free part of the plane, the robot should autonomously arrive at the isoline where an unknown scalar field assumes a given value. Afterwards, it should track the obstacle-free part of the isoline. The robot has access only to the field value at the current location and the distance from this location to the obstacles. We present a hybrid nonlinear navigation law that solves this mission. The law does not use estimation of the field gradient and is non-demanding with respect to both computation and motion. The non-local convergence of the proposed algorithm is rigorously justified and confirmed by computer simulation tests.     

Trajectory Modeling of Robot Manipulators in the Presence of Obstacles

This paper presents two different strategies for the problem of the optimal trajectory planning of robot manipulators in the presence of fixed obstacles. The first strategy is related to the situation where the trajectory must pass through a given number of points. The second strategy corresponds to the case where only the initial and final points are given. The optimal traveling time and the minimum mechanical energy of the actuators are considered together to build a multiobjective function. The trajectories are defined using spline functions and are obtained through offline computation for online operation. Sequential unconstrained minimization techniques (SUMT) have been used for the optimization. The obstacles are considered as three-dimensional objects sharing the same workspace performed by the robot. The obstacle avoidance is expressed in terms of the distances between potentially colliding parts. Simulation results are presented and show the efficiency of the general methodology used in this paper.     

Algorithmic and complexity issues of robot motion in an uncertain environment

This paper presents a survey of one approach to planning collision-free paths for an automaton operating in an environment with obstacles. Path planning is one of the central problems in robotics. Typically, the task is presented in the two- or three-dimensional space, with the automaton being either an autonomous vehicle or an arm manipulator with a fixed base. The multiplicity of approaches one finds in this area revolves around two basic models: in one, called path planning with complete information, perfect information about the geometry and positions of the robot and the obstacles is assumed, whereas in the other, called path planning with incomplete information, an element of uncertainty about the environment is present. The approach surveyed here, called dynamic path planning, has been developed in the last few years; it is based on the latter model and gives rise to algorithmic and computational issues very different from those in the former model. The approach produces provable (nonheuristic) path planning algorithms for an automaton operating in a highly unstructured environment where no knowledge about the obstacles is available beforehand and no constraints on the geometry of the obstacles are imposed.     

Generating optimal path by level set approach for a mobile robot moving in static/dynamic environments

According to the analogy between the mobile robot navigation path and the heat transferring path under steady state, the robot path planning problem during navigation is converted into identify the heat transferring path that minimizes the thermal compliance across the analysis domain. A new path planning approach which combines the concept of growth simulation and level set based heat conduction topology optimization framework is adopted to determine the heat transferring path. By introducing the concept of growth simulation, the proposed approach could calculate a few steps of the navigation path, which is of great significance for online reactive navigation. The proposed approach could avoid local minima and search for the optimal growth orientation freely without constraints from background mesh since the inherent characteristics of heat conduction and the level set approach, respectively. A new reactive navigation algorithm based on the proposed path planning approach and the concept of temporarily safe path is proposed to navigate the mobile robot from the start point to the goal point in unknown dynamic environment with static and dynamic obstacles. Diverse simulation cases are carried to illustrate the effectiveness of the reactive navigation algorithm.     

基于模糊传感器的机器人动态障碍环境中的运动控制

对自主式机械手在动态和部分已知且存在运动障碍环境中的运动规划和控制进行了研究,解决了自由碰撞运动控制中具有普遍意义的问题。利用人工势能场的机器人导航控制技术由模糊控制实现,系统的稳定性由李雅普诺夫原理保证。模糊控制器为机器人伺服提供控制指令,使机器人在不可预知的环境中能实时地、自主地选择到达目标的路径和方向。在动态环境的实时控制中,基于传感器的运动控制是处理未知模型和障碍物的重要控制方式。     

Paradox,programming, and learning probability: A case study in a connected mathematics framework

Formal methods abound in the teaching of probability and statistics. In the Connected Probability project, we explore ways for learners to develop their intuitive conceptions of core probabilistic concepts. This article presents a case study of a learner engaged with a probability paradox. Through engaging with this paradoxical problem, she develops stronger intuitions about notions of randomness and distribution and the connections between them. The case illustrates a Connected Mathematics approach: that primary obstacles to learning probability are conceptual and epistemological; that engagement with paradox can be a powerful means of motivating learners to overcome these obstacles; that overcoming these obstacles involves learners making mathematics—not learning a “received” mathematics and that, through programming computational models, learners can more powerfully express and refine their mathematical understandings.     

机器人路径规划算法及其应用

本文研究环境已知条件下的移动机器人路径规划问题,提出了一种基于人工神经网络的路径规划算法,所提算法可以规划出折线型的最短路径,并且计算简单,收敛速度快。将所提算法应用于机器人“Khepera“,通过模拟实验,表明所提算法有效。     

A “retraction” method for planning the motion of a disc

A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O(n log n) algorithm for planning an obstacle-avoiding motion of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.     

Optimal regularity in the obstacle problem for Kolmogorov operators related to American Asian options

In this paper we prove optimal interior regularity for solutions to the obstacle problem for a class of second order differential operators of Kolmogorov type. We treat smooth obstacles as well as non-smooth obstacles. All our proofs follow the same line of thought and are based on blow-ups, compactness, barriers and arguments by contradiction. The problem considered arises in financial mathematics, when considering path-dependent derivative contracts with early exercise feature.     

On the Invertible Boundary Integral Operator in the Exterior Impedance Problem for the Helmholtz Equation

We propose an approach for reduction of the impedance problem for propagative Helmholtz equation outside several obstacles to the uniquely solvable Fredholm integral equation of the second kind and index zero. The integral equation in this approach is derived by introducing auxiliary boundaries with an appropriate boundary conditions inside obstacles.     

Bacterial memetic algorithm for offline path planning of mobile robots

The goal of the path planning problem is to determine an optimal collision-free path between a start and a target point for a mobile robot in an environment surrounded by obstacles. This problem belongs to the group of combinatorial optimization problems which are approached by modern optimization techniques such as evolutionary algorithms. In this paper the bacterial memetic algorithm is proposed for path planning of a mobile robot. The objective is to minimize the path length and the number of turns without colliding with an obstacle. The representation used in the paper fits well to the algorithm. Memetic algorithms combine evolutionary algorithms with local search heuristics in order to speed up the evolutionary process. The bacterial memetic algorithm applies the bacterial operators instead of the genetic algorithm??s crossover and mutation operator. One advantage of these operators is that they easily can handle individuals with different length. The method is able to generate a collision-free path for the robot even in complicated search spaces. The proposed algorithm is tested in real environment.     

A social approach for target localization: simulation and implementation in the marXbot robot

Foraging is a common benchmark problem in collective robotics in which a robot (the forager) explores a given environment while collecting items for further deposition at specific locations. A typical real-world application of foraging is garbage collection where robots collect garbage for further disposal in pre-defined locations. This work proposes a method to cooperatively perform the task of finding such locations: instead of using local or global localization strategies relying on pre-installed infrastructure, the proposed approach takes advantage of the knowledge gathered by a population about the localization of the targets. In our approach, robots communicate in an intrinsic way the estimation about how near they are from a target; these estimations are used by neighbour robots for estimating their proximity, and for guiding the navigation of the whole population when looking for these specific areas. We performed several tests in a simulator, and we validated our approach on a population of real robots. For the validation tests we used a mobile robot called marXbot. In both cases (i.e., simulation and implementation on real robots), we found that the proposed approach efficiently guides the robots towards the pre-specified targets while allowing the modulation of their speed.     

A Constraint Programming Approach to Extract the Maximum Number of Non-Overlapping Test Forms

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented. An erratum to this article is available at .     

Honey-pot constrained searching with local sensory information

In this paper we investigate the problem of searching for a hidden target in a bounded region of the plane using an autonomous robot which is only able to use local sensory information. The problem is naturally formulated in the continuous domain but the solution proposed is based on an aggregation/refinement approach in which the continuous search space is partitioned into a finite collection of regions on which we define a discrete search problem. A solution to the original problem is obtained through a refinement procedure that lifts the discrete path into a continuous one.