The Auction Technique for the Sensor Based Navigation Planning of an Autonomous Mobile Robot

The problem of finding a path for the motion of a small mobile robot from a starting point to a fixed target in a two dimensional domain is considered in the presence of arbitrary shaped obstacles. No a priori information is known in advance about the geometry and the dimensions of the workspace nor about the number, extension and location of obstacles. The robot has a sensing device that detects all obstacles or pieces of walls lying beyond a fixed view range. A discrete version of the problem is solved by an iterative algorithm that at any iteration step finds the smallest path length from the actual point to the target with respect to the actual knowledge about the obstacles, then the robot is steered along the path until a new obstacle point interfering with the path is found, at this point a new iteration is started. Such an algorithm stops in a number of steps depending on the geometry, finding a solution for the problem or detecting that the problem is unfeasible. Since the algorithm must be applied on line, the effectiveness of the method depends strongly on the efficiency of the optimization step. The use of the Auction method speeds up this step greatly both for the intrinsic properties of this method and because we fully exploit a property relating two successive optimizations, proved on paper, that in practical instances enables the mean computational cost requested by the optimization step to be greatly reduced. It is proved that the algorithm converges in a finite number of steps finding a solution when the problem is feasible or detecting the infeasibility condition otherwise. Moreover the worst case computational complexity of the whole algorithm is shown to be polynomial in the number of nodes of the discretization grid. Finally numerical examples are reported in order to show the effectiveness of this technique.     

Pose estimation-based path planning for a tracked mobile robot traversing uneven terrains

A novel path-planning algorithm is proposed for a tracked mobile robot to traverse uneven terrains, which can efficiently search for stability sub-optimal paths. This algorithm consists of combining two RRT-like algorithms (the Transition-based RRT (T-RRT) and the Dynamic-Domain RRT (DD-RRT) algorithms) bidirectionally and of representing the robot–terrain interaction with the robot’s quasi-static tip-over stability measure (assuming that the robot traverses uneven terrains at low speed for safety). The robot’s stability is computed by first estimating the robot’s pose, which in turn is interpreted as a contact problem, formulated as a linear complementarity problem (LCP), and solved using the Lemke’s method (which guarantees a fast convergence). The present work compares the performance of the proposed algorithm to other RRT-like algorithms (in terms of planning time, rate of success in finding solutions and the associated cost values) over various uneven terrains and shows that the proposed algorithm can be advantageous over its counterparts in various aspects of the planning performance.     

Solution path for manifold regularized semisupervised classification

Traditional learning algorithms use only labeled data for training. However, labeled examples are often difficult or time consuming to obtain since they require substantial human labeling efforts. On the other hand, unlabeled data are often relatively easy to collect. Semisupervised learning addresses this problem by using large quantities of unlabeled data with labeled data to build better learning algorithms. In this paper, we use the manifold regularization approach to formulate the semisupervised learning problem where a regularization framework which balances a tradeoff between loss and penalty is established. We investigate different implementations of the loss function and identify the methods which have the least computational expense. The regularization hyperparameter, which determines the balance between loss and penalty, is crucial to model selection. Accordingly, we derive an algorithm that can fit the entire path of solutions for every value of the hyperparameter. Its computational complexity after preprocessing is quadratic only in the number of labeled examples rather than the total number of labeled and unlabeled examples.     

Relative localization using path odometry information

All mobile bases suffer from localization errors. Previous approaches to accommodate for localization errors either use external sensors such as lasers or sonars, or use internal sensors like encoders. An encoder’s information is integrated to derive the robot’s position; this is called odometry. A combination of external and internal sensors will ultimately solve the localization error problem, but this paper focuses only on processing the odometry information. We solve the localization problem by forming a new odometry error model for the synchro-drive robot then use a novel procedure to accurately estimate the error parameters of the odometry error model. This new procedure drives the robot through a known path and then uses the shape of the resulting path to estimate the model parameters. Experimental results validate that the proposed method precisely estimates the error parameters and that the derived odometry error model of the synchro-drive robot is correct. Nakju Lett Doh received his BS, his MS, and his Ph.D. degree in Mechanical Engineering from Pohang University of Science and Technology (POSTECH), KOREA, in 1998, 2000, and 2005, respectively. Since then, he is a senior researcher in Intellgient Robot Reserarch Division, Electronics and Telecommunications Research Institute (ETRI), KOREA. He received the glod prize in Intelligent Robot Contest hosted by Northern KyoungSang Province at 2000 and the gold prize in Humantech Thesis Competition hosted by Samsung Electronics at 2005. In 2003, he got the best student paper award in IEEE International Conference on Robotics and Automation held in Taiwan. His research interests are the localization and navigation of mobile robots and ubiquitous robotic space for intelligent robot navigation. Howie Choset is an Associate Professor of Robotics at Carnegie Mellon University where he conducts research in motion planning and design of serpentine mechanisms, coverage path planning for de-mining and painting, mobile robot sensor based exploration of unknown spaces, and education with robotics. In 1997, the National Science Foundation awarded Choset its Career Award to develop motion planning strategies for arbitrarily shaped objects. In 1999, the Office of Naval Research started supporting Choset through its Young Investigator Program to develop strategies to search for land and sea mines. Recently, the MIT Technology Review elected Choset as one of its top 100 innovators in the world under 35. Choset directs the Undergraduate Robotics Minor at Carnegie Mellon and teaches an overview course on Robotics which uses series of custom developed Lego Labs to complement the course work. Professor Choset’s students have won best paper awards at the RIA in 1999 and ICRA in 2003. Finally, Choset is a member of an urban search and rescue response team using robots with the Center for Robot Assisted Search and Rescue. Now, he is active in extending the mechanism design and path planning work to medical mechatronics. Wan Kyun Chung received his BS degree in Mechanical Design from Seoul National University in 1981, his MS degree in Mechanical Engineering from KAIST in 1983, and his Ph.D. in Production Engineering from KAIST in 1987. He is Professor in the school of Mechanical Engineering, POSTECH (he joined the faculty in 1987). In 1988, he was a visiting professor at the Robotics Institute of Carnegie-Mellon University. In 1995 he was a visiting scholar at the university of California, Berkeley. His research interests include the localization and navigation for mobile robots, underwater robots and development of robust controller for precision motion control. He is a director of National Research Laboratory for Intelligent Mobile Robot Navigation. He is serving as an Associate Editor for IEEE Tr. on Robotics, international editorial board for Advanced Robotics.     

Reduction of free-space-loss for good and rapid 3D path planning of 6DOF robots

This paper deals with a new approach to solve the up to 6DOF robots global collision-free path planning. This problem seems to be more difficult when big or very long pieces are manipulated in cluttered and occupied environments. Moreover, the computational effort increases if the necessary path resolution is very high. The developed algorithm is based on the c-space technique. Different robot models are used for rapid c-spaces computation. Each one for different parts of a typical pick and place task. The algorithm selectively uses these global or local c-spaces. This strategy leads to fast global c-space computation without a considerable loss of free-space caused by the simplified robot model, and to quasi real-time local c-space computation. The paths searching in the computed c-spaces can be performed by several techniques: cell (cube) mapping, octree, and slice, which are rule-base selected in an adequate way. Finally, the results of the algorithm implementation in several real robots are presented.     

Remarks on the application of dynamic programming to the optimal path timing of robot manipulators

In this paper, we investigate the use of the dynamic programming approach in the solution of the optimal path timing problem in robotics. This problem is computationally feasible because the path constraint reduces the dimension of the state in the problem to two. The Hamilton–Jacobi–Bellman equation of dynamic programming, a nonlinear first order partial differential equation, is presented and is solved approximately using finite difference methods. Numerical solution of this results in the optimal policy which can then be used to define the optimal path timing by numerical integration. Issues relating to the convergence of the numerical schemes are discussed, and the results are applied to an experimental SCARA manipulator. © 1998 John Wiley & Sons, Ltd.     

Mobile robot path planning with surrounding point set and path improvement

The objective of the path planning problem for a mobile robot is to generate a collision-free path from a starting position to a target position with respect to a certain fitness function, such as distance. Although, over the last few decades, path planning has been studied using a number of methodologies, the complicated and dynamic environment increases the complexity of the problem and makes it difficult to find an optimal path in reasonable time. Another issue is the existence of uncertainty in previous approaches. In this paper, we propose a new methodology to solve the path planning problem in two steps. First, the surrounding point set (SPS) is determined where the obstacles are circumscribed by these points. After the initial feasible path is generated based on the SPS, we apply a path improvement algorithm depending upon the former and latter points (PI_FLP), in which each point in the path is repositioned according to two points on either side. Through the SPS, we are able to identify the necessary points for solving path planning problems. PI_FLP can reduce the overall distance of the path, as well as achieve path smoothness. The SPS and PI_FLP algorithms were tested on several maps with obstacles and then compared with other path planning methods As a result, collision-free paths were efficiently and consistently generated, even for maps with narrow geometry and high complexity.     

The constrained shortest path tour problem

In this paper, we study the constrained shortest path tour problem. Given a directed graph with non-negative arc lengths, the aim is to find a single-origin single-destination shortest path, which needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be of different size. In addition, it is required that the path does not include repeated arcs.Theoretical properties of the problem are studied, proving that it belongs to the complexity class NP-complete. To exactly solve it, a Branch & Bound method is proposed. Given the problem hardness, a Greedy Randomized Adaptive Search Procedure is also developed to find near-optimal solutions for medium to large scale instances.Extensive computational experiments, on a significant set of test problems, are carried out in order to empirically evaluate the performance of the proposed approaches. The computational results show that the Greedy Randomized Adaptive Search Procedure is effective in finding optimal or near optimal solutions in very limited computational time.     

An enhanced exact procedure for the absolute robust shortest path problem

The aim of this paper is to investigate the use of heuristic information to efficiently solve to optimality the robust shortest path problem. Starting from the exact algorithm proposed by Murty and Her, we describe how this algorithm can be enhanced by using heuristic rules and evaluation functions to guide the search. The efficiency of the proposed enhanced approach is tested over a range of random generated instances. Our computational results indicate that the use of heuristic criteria is able to speed up considerably the search and that the enhanced exact solution method outperforms the state‐of‐the‐art algorithm proposed by Murty and Her in most of the instances.     

Combining path planners and motion graphs

Natural locomotion of virtual characters is very important in games and simulations. The naturalness of the total motion strongly depends on both the path the character chooses and the animation of the walking character. Therefore, much work has been done on path planning and generating walking animations. However, the combination of both fields has received less attention. Combining path planning and motion synthesis introduces several problems. In this paper, we will identify two problems and propose possible solutions. The first problem is selecting an appropriate distance metric for locomotion synthesis. When concatenating clips of locomotion, a distance metric is required to detect good transition points. We have evaluated three common distance metrics both quantitatively (in terms of footskating, path deviation and online running time) and qualitatively (user study). Based on our observations, we propose a set of guidelines when using these metrics in a motion synthesizer. The second problem is the fact that there is no single point on the body that can follow the path generated by the path planner without causing unnatural animations. This raises the question how the character should follow the path. We will show that enforcing the pelvis to follow the path will lead to unnatural animations and that our proposed solution, which uses path abstractions, generates significantly better animations. Copyright © 2011 John Wiley & Sons, Ltd.     

基于路径预测的机器人足球路径规划

针对常用的机器人路径规划算法过于复杂并且在每个运动周期都计算路径的问题,提出了一种结合路径预测的路径最优算法.充分利用预测结果减少每周期的路径规划时间;用微量调整动态控制机器人左右轮速度,并充分利用折线路径的短距离优势,为避障机器人创建一条最短路径;以基于周期性预测在同个时间轴上的相交作为碰撞信号,来减少每个周期的重复性计算时间.实验结果表明,该方法能大大提高机器人路径规划的速度,降低不同周期上路径规划结果不一致导致的运动震荡.     

Enhanced path smoothing based on conjugate gradient descent for firefighting robots in petrochemical complexes*

The firefighting robot system (FFRS) comprises several autonomous robots that can be deployed to fire disasters in petrochemical complexes. For autonomous navigation, the path planner should consider the robot constraints and characteristics. Specifically, three requirements should be satisfied for a path to be suitable for the FFRS. First, the path must satisfy the maximum curvature constraint. Second, it must be smooth for robots to easily execute the trajectory. Third, it must allow reaching the target location in a specific heading. We propose a path planner that provides smooth paths, satisfy the maximum curvature constraint, and allows a suitable robot heading. The path smoother is based on the conjugate gradient descent, and three approaches are proposed for this path planner to meet all the FFRS requirements. The effectiveness of these approaches is qualitatively and quantitatively evaluated by examining the generated paths. Finally, the path planner is applied to an actual robot to verify the suitability of the generated paths for the FFRS, and planning is applied to another type of robot to demonstrate the wide applicability of the proposed planner.     

A robust control scheme for asymptotic tracking of robot motion

In this paper, a controller structure is developed to provide for asymptotic tracking of robot motion. The design tool is the theory of hyperstability and the analysis has led to a simple and an easy-to-implement robust version of the inverse dynamics. Simulation studies are worked out to demonstrate the controller performance. A comparison with other methods is done to show the merits of the developed scheme vs. other recently developed schemes. The implementation and computational requirements of the control schemes are determined and shown to be within the capabilities of new control hardware.This work was supported by the Kuwait University Research Administration under Grant No. EE063.     

A new 2-point absolute pose estimation algorithm under planar motion

Several pose estimation algorithms, such as n-point and perspective n-point (PnP), have been introduced over the last few decades to solve the relative and absolute pose estimation problems in robotics research. Since the n-point algorithms cannot decide the real scale of robot motion, the PnP algorithms are often addressed to find the absolute scale of motion. This paper introduce a new PnP algorithm which use only two 3D–2D correspondences by considering only planar motion. Experiment results prove that the proposed algorithm solves the absolute motion in real scale with high accuracy and less computational time compared to previous algorithms.     

机器人路径规划的新型头脑风暴优化算法

针对头脑风暴优化算法在求解机器人路径规划问题时存在初始解成功率低、运算代价大且路径不平滑等问题进行了研究,从心理学角度出发,提出了一种新型头脑风暴优化算法及其离散化方案。引入羊群效应下的教与学思想增强个体学习的方向性,并通过基于自我选择效应的步长调节机制扩大后期局部搜索比例,提升算法效率;离散处理阶段采用贪婪移动搜索法取得较优初始解,重新定义运算过程以双向平滑路径。仿真结果表明,新型头脑风暴优化算法在离散化前后均有较优的表现,在不同障碍物环境中均能规划出较优的路径。数值实验验证了所提算法的有效性,该算法在路径规划领域的应用值得进一步探索。     

带拖车移动机器人全局路径跟踪控制

研究带拖车移动机器人的前向路径跟踪控制和倒车路径跟踪控制问题.首先建立系统的运动学模型,并进行系统的运动特性分析;然后基于Lyapunov方法提出一种新的单体移动机器人全局路径跟踪控制器,并将其引入带拖车移动机器人的前向路径跟踪控制;再后通过运动学变换,实现了拖挂任意节拖车的系统的倒车路径跟踪控制;最后针对三车体系统的两种路径跟踪控制进行仿真,结果表明了该方法的有效性.     

Acquisition of manipulative grounded symbols for integration of symbolic processing and stimulus-reaction type parallel processing

The architecture constructed with two types of processing, logical symbol processing and stimulus-reaction type parallel processing, seems promising for intelligent systems. Since symbol processing is constructed by a top-down approach and stimulus-reaction type processing is built up by a bottom-up approach, a discrepancy, which is called the 'symbol grounding problem', takes place. This paper presents a framework for integration of symbol processing and stimulus-reaction type processing from the viewpoint of solving the symbol grounding problem. In this framework designers or users use the conventional heuristic symbols and the systems use the self-organized symbols based on the characteristics/environment of the systems themselves. Translation from one to another produces the fusion of those two symbols. The self-organized symbols are grounded and manipulative. Navigation of an autonomous robot is simulated. Acquisition of manipulative grounded symbols with the proposed framework is demonstrated. Since the constructed robot is equipped only with a stimulus-reaction type controller, it has a robustness against noise and temporary geometrical changes.     

Intelligent Robot Vision Sensors in VLSI

Traditional approaches for solving real-world problems using computer vision have depended heavily on CCD cameras and workstations. As the computation power of workstations doubles every 1.5 years, they are now better able to handle the large amount of data presented by the cameras; yet real-time solutions for physical interaction with the real-world continues to be very hard, and relegated to large and expensive systems. Our approach attempts to solve this problem by using computational sensors and small/inexpensive embedded processors. The computational sensors are custom designed to reduce the amount of data collected, to extract only relevant information and to present this information to the simple processor, microcontrollers (Cs) or DSPs, in a format which reduces post-processing latency. Consequently, the post-processors are required to perform only high level computation on features rather than data. These systems are applied to problems such as target acquisition and tracking for image stabilization and autonomous data driven autonavigation for mobile robots. We present an example of a system that uses a pair of computational sensors and a C to solve a toy autonavigation problem.The computational sensors, however, have wide applications in many problems that require image preprocessing such as edge detection, motion detection, centroid localization and other spatiotemporal processing. This paper also presents a general-purpose computational sensor capable of extracting many visual information components at the focal plane.     

Optimal Motion Planning of Robotic Manipulators Removing Mobile Objects Grasped in Motion

The following study deals with motion optimization of robot arms having to transfer mobile objects grasped when moving. This approach is aimed at performing repetitive transfer tasks at a rapid rate without interrupting the dynamics of both the manipulator and the moving object. The junction location of the robot gripper with the object, together with grasp conditions, are partly defined by a set of local constraints. Thus, optimizing the robot motion in the approach phase of the transfer task leads to the statement of an optimal junction problem between the robot and the moving object. This optimal control problem is characterized by constrained final state and unknown traveling time. In such a case, Pontryagin"s maximum principle is a powerful mathematical tool for solving this optimization problem. Three simulated results of removing a mobile object on a conveyor belt are presented; the object is grasped in motion by a planar three-link manipulator.     

Adaptation and learning in control of voluntary movement by the central nervous system

In order to control voluntary movements, the central nervous system must solve the following three computational problems at different levels: (1) the determination of a desired trajectory in visual coordinates; (2) the transformation of its coordinates into body coordinates; and (3) the generation of motor command. Concerning these problems, relevant experimental observations obtained in the field of neuroscience are briefly reviewed. On the basis of physiological information and previous models, we propose computational theories and a neural network model which account for these three problems. (1) A minimum torque-change model which predicts a wide range of trajectories in human multi-joint arm movements is proposed as a computational model for trajectory formation. (2) An iterative learning scheme is presented as an algorithm which solves the coordinate transformation and the control problem simultaneously. This algorithm can be regarded as a Newton-like method in function spaces. (3) A neural network model for generation of motor command is proposed. This model contains internal neural models of the motor system and its inverse system. The inverse-dynamics model is acquired by heterosynaptic plasticity using a feedback motor command (torque) as an error signal. The hierarchical arrangement of these neural networks and their global control are discussed. Their applications to robotics are also discussed.