A gradient-based path optimization method for motion planning

Most algorithms in probabilistic sampling-based path planning compute collision-free paths made of straight line segments lying in the configuration space. Due to the randomness of sampling, the paths make detours that need to be optimized. The contribution of this paper is to propose a basic gradient-based algorithm that transforms a polygonal collision-free path into a shorter one. While requiring only collision checking, and not any time-consuming obstacle distance computation nor geometry simplification, we constrain only part of the configuration variables that may cause a collision, and not entire configurations. Thus, parasite motions that are not useful for the problem resolution are reduced without any assumption. Experimental results include navigation and manipulation tasks, eg a manipulator arm-filling boxes and a PR2 robot working in a kitchen environment. Comparisons with a random shortcut optimizer and a partial shortcut have also been studied.     

机械臂最优运动规划问题的混合求解

提出一种基于GA和SQP求解机械臂最优运动规划问题的混合算法．首先采用B样条函数逼近关节运动轨迹，将最优控制问题转化为有约束的非线性规划问题，然后引入基于种群的GA算法，给出全局最优解的初始估计；最后利用序列二次规划(SQP)得到高精度全局最优解．仿真结果表明该方法优于单纯的GA或SQP方法。     

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.     

基于传感器的非完整移动机器人运动规划

针对非完整移动机器人在未知室内环境中提出了一种路径规划方法, 通过利用传感器对周围环境的探测和实时处理传感器数据, 以及所设计的目标寻找函数, 可以有效地完成其运动规划. 该方法能够确保移动机器人在无障碍物区或障碍物对机器人不构成危险时加速前进, 在障碍物区能够慢速绕过, 从而使得移动机器人快速且安全地到达目标位置, 仿真的结果证明了该方法的有效性.     

新的室内移动机器人的实时定位和运动规划方法

提出了一种将传感器信息与先验环境信息融合实现移动机器人定位和运动规划的方法.这种方法选用SICK LMS200型激光扫描测距仪为机器人感知装置,根据室内障碍物的顶点或拐角信息进行定位和运动规划.这种定位和规划方法模仿了盲人在熟悉环境下用拐杖走路的过程,适于室内移动机器人的实时定位和运动规划.     

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.     

非完整移动机器人鲁棒运动规划

非完整移动机器人利用传感器可以解决不确定性模型和未知环境中的许多问题. 利用移动机器人上配备的传感器的信息组合提出了一种在线视点寻求算法, 结合移动机器人的运动方程和传感器的量测方程采用扩展Kalman估计来对移动机器人的位置进行修正, 以降低运动的不确定性, 从而得到一种鲁棒的规划算法, 仿真的结果证明了上述方法是行之有效的.     

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.     

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.     

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.     

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.

改进人工势场的手术机器人位姿规划

运动避障与路径规划是手术机器人自动化手术中重要的技术环节,为机器人手术提供了良好的术中安全性及准确性.本研究针对上述两关键技术,提出改进人工势场的手术机器人位姿规划算法,首先,通过对引力函数进行改进,在不求取运动学逆解的情况下,能够准确驱动机械臂到达指定位姿;接着,利用快速凸包算法将障碍物凸体化,通过Gilbert Johnson Keerthi (GJK)算法计算障碍物与机械臂连杆等效圆柱面之间的最近距离,使避障距离更加准确;然后,通过自适应步长,使机械臂运动更加平稳快速;最后,引入动态引力常数,使机械臂具有逃离局部极小值的能力.实验结果表明,本研究能够让机器人在避障情况下平稳快速到达规划位姿,并在陷入局部极小值时逃逸,为未来医疗机器人在自动化手术方面提供了新思路.     

三连杆移动机械臂模型与运动规划

采用拉格朗日动力学方法和非完整动力学罗兹方程建立了三连杆移动机器臂运动学和动力学模型,并且利用该模型采用了人工势函数方法来驱动移动机械臂系统绕过障碍物到达目标位置.仿真的结果证明了该模型的正确性及其规划方法是有效的.     

度量区间时序逻辑下四旋翼的集成任务与运动规划

本文采用优化方法解决度量区间时序逻辑下进行四旋翼的集成任务与运动规划问题。传统方法通常将任务约束和运动约束分层处理。由于不同规划层所使用的抽象模型并不完全匹配,任务规划层求解出的高层策略往往无法有效地被低层的运动规划层执行,从而只能找到次优的运动轨迹甚至找不到解。本文摒弃分层规划的策略,采用B样条拟合运动轨迹,将问题转化问一个混合整数线性规划问题,直接在同一层处理带有时序逻辑的任务约束以及运动约束。与其他现有方法对比,我们的方法保证了连续时间下的轨迹也可以完全满足所有约束条件,而非只有离散的轨迹点才可以满足。我们用四旋翼模型进行了一系列仿真验证,仿真结果表明了方法的有效性     

广义Voronoi图求解多机器人运动规划

在拥挤环境中,由于障碍物的边界形状比较复杂,需要使用广义Voronoi图表示空间环境。且在多移动机器人的运动规划过程中,需要协调多个机器人的运动,必须得到Voronoi图通道的宽度。为此提出了一种计算拥挤障碍物环境中生成的广义Voronoi图及其通道宽度的算法。并在生成的Voronoi图上利用A*算法对多个机器人进行路径规划,并利用分布式方法协调多个机器人运动。对协调两个机器人运动的过程进行了仿真,仿真结果表明利用提出的算法生成的具有通道宽度信息的Voronoi图能够满足多移动机器人运动规划的需要。