Graph-based optimal reconfiguration planning for self-reconfigurable robots

The goal of optimal reconfiguration planning (ORP) is to find a shortest reconfiguration sequence to transform a modular and reconfigurable robot from an arbitrary configuration into another. This paper investigates this challenging problem for chain-type robots based on graph representations and presents a series of theoretical results: (1) a formal proof that this is an NP-complete problem, (2) a reconfiguration planning algorithm called MDCOP which generates the optimal graph-based reconfiguration plan, and (3) another algorithm called GreedyCM which can find a near-optimal solution in polynomial time. Experimental and statistical results demonstrate that the solutions found by GreedyCM are indeed near-optimal and the approach is computationally feasible for large-scale robots.     

An optimal algorithm for two robots path planning problem on the grid

This paper is a study on the problem of path planning for two robots on a grid. We consider the objective of minimizing the maximum path length which corresponds to minimizing the arrival time of the last robot at its goal position. We propose an optimal algorithm that solves the problem in linear time with respect to the size of the grid. We show that the algorithm is complete; meaning that it is sure to find an optimal solution or report if any does not exist.     

An efficient algorithm for one-step planar compliant motion planning with uncertainty

Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give anO(n ² logn) algorithm to find a single commanded motion direction that will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.A preliminary version of this paper appeared in theProceedings of the ACM Symposium on Computational Geometry, Saarbrücken, June 1989. This paper describes research done in the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research is provided in part by the National Science Foundation under Grant IRI-8802390 and by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute.     

An efficient approach to incorporating interfraction motion in IMRT treatment planning

Intensity modulated radiation therapy (IMRT) is one of the most widely used delivery modalities for radiation therapy for cancer patients. A patient is typically treated in daily fractions over a period of 5-9 weeks. In this paper, we consider the problem of accounting for changes in patient setup location and internal geometry between the treatment fractions, usually referred to as interfraction motion. The conventional method is to add a margin around the clinical tumor volume (CTV) to obtain a planning target volume (PTV). A fluence map optimization (FMO) model is then solved to determine the optimal intensity profiles to deliver to the patient. However, a margin-based method may not adequately model the changes in dose distributions due to the random nature of organ motion. Accounting for interfraction motion in the FMO model essentially transforms the deterministic optimization problem into a stochastic one. We propose a stochastic FMO model that employs convex penalty functions to control the treatment plan quality and uses a large number of scenarios to characterize interfraction motion uncertainties. Some effects of radiotherapy are impacted mainly by the dose distribution in a given treatment fraction while others tend to manifest themselves over time and depend mostly on the total dose received over the course of treatment. We will therefore formulate an optimization model that explicitly incorporates treatment plan evaluation criteria that apply to the total dose received over all treatment fractions and ones that apply to the dose per fraction. Particularly when many structures fall into the former category, this can lead to significant reductions in the dimension of the optimization model and therefore the time required to solve it. We test an example of our model on five clinical prostate cancer cases, showing the efficacy of our approach. In particular, compared to a traditional margin-based treatment plan, our plans exhibit significantly improved target dose coverage and clinically equivalent critical structure sparing at only a modest increase in computational effort.     

Optimum motion planning in joint space for robots using genetic algorithms

The optimum motion planning in joint space (OMPJS) for robots, which generally consists of two subproblems, optimum path planning and optimum trajectory planning, was considered as a whole in the paper. A new method for optimum motion planning problem based on an improved genetic algorithm is proposed, which is more general, flexible and effective. This approach incorporates kinematics constraints, dynamics constraints, and control constraints of robotic manipulator. The simulation results for a two and a three degrees of freedom robots are presented and discussed. The simulations are based on genetic algorithm class library WGAClass 1.0 developed by us with Borland C++ 3.1.     

Dual hierarchical genetic-optimal control: A new global optimal path planning method for robots

A new two-stage analytical-evolutionary algorithm considering dynamic equations is presented to find global optimal path. The analytical method is based on the indirect open loop optimal control problem and the evolutionary method is based on genetic algorithm (GA). Initial solutions, as start points of optimal control problem, are generated by GA to be used by optimal control. Then, a new sub-optimal path is generated through optimal control. The cost function is calculated for every optimal solution and the best solutions are chosen for the next step. The obtained path is used by GA to produce new generation of start points. This process continues until the minimum cost value is achieved. In addition, a new GA operator is introduced to be compatible with optimal control. It is used to select the pair chromosomes for crossover. The proposed method eliminates the problem of optimal control (being trapped in locally optimal point) and problem of GA (lack of compatibility with analytical dynamic equations). Hence problem is formulated and verification is done by comparing the results with a recent work in this area. Furthermore effectiveness of the method is approved by a simulation study for spatial non-holonomic mobile manipulators through conventional optimal control and the new proposed algorithm.     

Anytime motion planning for prehensile manipulation in dense clutter

ABSTRACT

Many methods have been developed for planning the motion of robotic arms for picking and placing, ranging from local optimization to global search techniques, which are effective for sparsely placed objects. Dense clutter, however, still adversely affects the success rate, computation times, and quality of solutions in many real-world setups. The proposed method achieves high success ratio in clutter with anytime performance by returning solutions quickly and improving their quality over time. The method first explores the lower dimensional end effector's task space efficiently by ignoring the arm, and build a discrete approximation of a navigation function. This is performed online, without prior knowledge of the scene. Then, an informed sampling-based planner for the entire arm uses Jacobian-based steering to reach promising end effector poses given the task space guidance. This process is also comprehensive and allows the exploration of alternative paths over time if the task space guidance is misleading. This paper evaluates the proposed method against alternatives in picking or placing tasks among varying amounts of clutter for a variety of robotic manipulators with different end-effectors. The results suggest that the method reliably provides higher quality solution paths quicker, with a higher success rate relative to alternatives.     

Task-oriented motion planning for multi-arm robotic systems

In this paper a task-oriented motion planning approach for general cooperative multi-robot systems is proposed. In order to derive a meaningful task formulation, a taxonomy of cooperative multi-arm systems of industrial interest is devised. Then, a workpiece-oriented general formulation for cooperative tasks is proposed, where the user is asked to specify the motion of the system only at the workpiece level, while the motion of the single arms in the system is computed via kinematic transformations between the relevant coordinate frames. Based on this task formulation, an instructions set is derived to extend classical programming languages for industrial robots to general multi-robot systems. In order to test the approach, a software environment has been built, composed of an interpreter of the language and the motion planning software.     

Modeling dynamic scenarios for local sensor-based motion planning

This paper addresses the modeling of the static and dynamic parts of the scenario and how to use this information with a sensor-based motion planning system. The contribution in the modeling aspect is a formulation of the detection and tracking of mobile objects and the mapping of the static structure in such a way that the nature (static/dynamic) of the observations is included in the estimation process. The algorithm provides a set of filters tracking the moving objects and a local map of the static structure constructed on line. In addition, this paper discusses how this modeling module is integrated in a real sensor-based motion planning system taking advantage selectively of the dynamic and static information. The experimental results confirm that the complete navigation system is able to move a vehicle in unknown and dynamic scenarios. Furthermore, the system overcomes many of the limitations of previous systems associated to the ability to distinguish the nature of the parts of the scenario.

A learning fuzzy algorithm for motion planning of mobile robots

A sensor-based fuzzy algorithm is proposed to navigate a mobile robot in a 2-dimensional unknown environment filled with stationary polygonal obstacles. When the robot is at the starting point, vertices of the obstacles that are visible from the robot are scanned by the sensors and the one with the highest priority is chosen. Here, priority is an output fuzzy variable whose value is determined by fuzzy rules. The robot is then navigated from the starting point to the chosen vertex along the line segment connecting these two points. Taking the chosen vertex as the new starting point, the next navigation decision is made. The navigation process will be repeated until the goal point is reached.In implementation of fuzzy rules, the ranges of fuzzy variables are parameters to be determined. In order to evaluate the effect of different range parameters on the navigation algorithm, the total traveling distance of the robot is defined as the performance index first. Then a learning mechanism, which is similar to the simulated annealing method in the neural network theory, is presented to find the optimal range parameters which minimize the performance index. Several simulation examples are included for illustration.     

An interactive tool for mobile robot motion planning

This paper presents an interactive tool aimed at facilitating the understanding of several well-known algorithms and techniques involved in solving mobile robot motion problems. These range from those modelling the mechanics of mobility to those used in navigation. The tool focuses on describing these problems in a simple manner in order to be useful for education purposes among different disciplines. By highlighting interactivity, the tool provides a novel means to study robot motion planning ideas in a manner that enhances full understanding. Furthermore, the paper discuses how the tool can be used in an introductory course of mobile robotics.     

基于局部传感和通讯的多机器人运动规划框架

在多机器人系统的研究中,基于局部传感和通讯的系统需要特殊的设计。针对许多任务都需要的运动规划能力,一个基于局部传感和通讯的完整框架在文中得到了描述和模拟实现。该框架包括环境模型、一个分布式架构、动态网络通讯模块和规划、协调算法;动态网络通讯模块为协调提供了良好基础,环境模型和规划、协调算法的设计都考虑到了局部传感和通讯的特殊性;对于框架的验证,提出了一个基于黑板架构的仿真模型并做出了实现。     

Periodic motion planning and control for underactuated mechanical systems

We consider the problem of periodic motion planning and of designing stabilising feedback control laws for such motions in underactuated mechanical systems. A novel periodic motion planning method is proposed. Each state is parametrised by a truncated Fourier series. Then we use numerical optimisation to search for the parameters of the trigonometric polynomial exploiting the measure of discrepancy in satisfying the passive dynamics equations as a performance index. Thus an almost feasible periodic motion is found. Then a linear controller is designed and stability analysis is given to verify that solutions of the closed-loop system stay inside a tube around the planned approximately feasible periodic trajectory. Experimental results for a double rotary pendulum are shown, while numerical simulations are given for models of a spacecraft with liquid sloshing and of a chain of mass spring system.     

A framework for multi-robot motion planning from temporal logic specifications

We propose a framework for the coordination of a network of robots with respect to formal requirement specifications expressed in temporal logics.A regular tessellation is used to partition the space of interest into a union of disjoint regular and equal cells with finite facets,and each cell can only be occupied by a robot or an obstacle.Each robot is assumed to be equipped with a finite collection of continuous-time nonlinear closed-loop dynamics to be operated in.The robot is then modeled as a hybrid automaton for capturing the finitely many modes of operation for either staying within the current cell or reaching an adjacent cell through the corresponding facet.By taking the motion capabilities into account,a bisimilar discrete abstraction of the hybrid automaton can be constructed.Having the two systems bisimilar,all properties that are expressible in temporal logics such as Linear-time Temporal Logic,Computation Tree Logic,and μ -calculus can be preserved.Motion planning can then be performed at a discrete level by considering the parallel composition of discrete abstractions of the robots with a requirement specification given in a suitable temporal logic.The bisimilarity ensures that the discrete planning solutions are executable by the robots.For demonstration purpose,a finite automaton is used as the abstraction and the requirement specification is expressed in Computation Tree Logic.The model checker Cadence SMV is used to generate coordinated verified motion planning solutions.Two autonomous aerial robots are used to demonstrate how the proposed framework may be applied to solve coordinated motion planning problems.     

一种基于遗传算法的欠驱动机器人避障运动规划新方法*

对平面欠驱动机器人的避障运动规划问题进行了研究,提出了一种利用遗传算法解决此类系统避障问题的新方法。通过引入虚拟弹簧—阻尼系统,在障碍物存在的情况下对系统非完整约束方程的广义力进行修正,采用部分稳定规划器进行运动规划,建立了基于能量的适应度函数,并利用遗传算法对提出的适应度函数进行全局优化,得到了部分稳定规划器的最优切换顺序,进而实现了欠驱动机器人的无碰撞路径规划。最后以平面3R欠驱动机器人为例进行了仿真实验,验证了该方法的有效性。     

Optimal motion planning for parallel robots via convex optimization and receding horizon

In this paper, the problem of motion planning for parallel robots in the presence of static and dynamic obstacles has been investigated. The proposed algorithm can be regarded as a synergy of convex optimization with discrete optimization and receding horizon. This algorithm has several advantages, including absence of trapping in local optimums and a high computational speed. This problem has been fully analyzed for two three-DOF parallel robots, ie 3s-RPR parallel mechanism and the so-called Tripteron, while the shortest path is selected as the objective function. It should be noted that the first case study is a parallel mechanism with complex singularity loci expression from a convex optimization problem standpoint, while the second case is a parallel manipulator for which each limb has two links, an issue which increases the complexity of the optimization problem. Since some of the constraints are non-convex, two approaches are introduced in order to convexify them: (1) A McCormick-based relaxation merged with a branch-and-prune algorithm to prevent it from becoming too loose and (2) a first-order approximation which linearizes the non-convex quadratic constraints. The computational time for the approaches presented in this paper is considerably low, which will pave the way for online applications.     

Optimal and suboptimal motion planning for collision avoidance of mobile robots in non-stationary environments

An optimal control formulation of the problem of collision avoidance of mobile robots moving in terrains containingmoving obstacles is presented. A dynamic model of the mobile robot and the dynamic constraints are derived. Collision avoidance is guaranteed if the minimum distance between the robot and the objects is nonzero. A nominal trajectory is assumed to be known from off-line planning. The main idea is to change the velocity along the nominal trajectory so that collisions are avoided. Furthermore, time consistency with the nominal plan is desirable. Two solutions are obtained: (1) A numerical solution of the optimization problem and a perturbation type of control to update the optimal plan and (2) A computationally efficient method giving near optimal solutions. Simulation results verify the value of the proposed strategies and allow for comparisons.     

A visual tool for computer supported learning: The robot motion planning example

We introduce an effective computer aided learning visual tool (CALVT) to teach graph-based applications. We present the robot motion planning problem as an example of such applications. The proposed tool can be used to simulate and/or further to implement practical systems in different areas of computer science such as graphics, computational geometry, robotics and networking. In the robot motion planning example, CALVT enables users to setup the working environment by creating obstacles and a robot of different shapes, specifying starting and goal positions, and setting other path or environment parameters from a user-friendly interface. The path planning system involves several phases. Each of these modules is complex and therefore we provide the possibility of visualizing graphically the output of each phase. Based on our experience, this tool has been an effective one in classroom teaching. It not only cuts down, significantly, on the instructor’s time and effort but also motivates senior/graduate students to pursue work in this specific area of research.     

An optimal control method for linear systems with time delay

An optimal control method for linear systems with time delay is developed in this paper. In the proposed control method, the differential equation with time delay of the system dynamics is first rewritten into a form without any time delay through a particular transformation. Then, the optimal controller is designed by using the classical optimal control theory. A numerical algorithm for control implementation is presented, since the obtained expression of the optimal controller contains an integral term that is not convenient for online calculation. The time delay is considered at the very beginning of the control design, and no approximation and estimation are made in the control system. Thus the system performance and stability are prone to be guaranteed. Instability in responses might occur only if a system with time delay is controlled by the optimal controller that was designed with no consideration of time delay. The effectiveness of the proposed optimal controller is demonstrated by simulation studies.