Dynamically-Stable Motion Planning for Humanoid Robots

We present an approach to path planning for humanoid robots that computes dynamically-stable, collision-free trajectories from full-body posture goals. Given a geometric model of the environment and a statically-stable desired posture, we search the configuration space of the robot for a collision-free path that simultaneously satisfies dynamic balance constraints. We adapt existing randomized path planning techniques by imposing balance constraints on incremental search motions in order to maintain the overall dynamic stability of the final path. A dynamics filtering function that constrains the ZMP (zero moment point) trajectory is used as a post-processing step to transform statically-stable, collision-free paths into dynamically-stable, collision-free trajectories for the entire body. Although we have focused our experiments on biped robots with a humanoid shape, the method generally applies to any robot subject to balance constraints (legged or not). The algorithm is presented along with computed examples using both simulated and real humanoid robots.     

基于变维度状态空间的增量启发式路径规划方法研究

在移动机器人路径规划中需要考虑运动几何约束,同时,由于它经常工作于动态、时变的环 境中,因此,还必须保证路径规划算法的效率.本文提出了一种基于变维度状态空间的增量启发式路径规划 方法,该方法既能满足移动机器人的运动几何约束,又能保证规划算法的效率.首先,设计了变维度状态空间, 在机器人周围的局部区域考虑运动几何约束组织高维状态空间,其他区域组织低维状态空间;然后,基于变维 度状态空间,提出了一种增量启发式路径规划方法,该方法在新的规划进程中可以使用以前的规划结果,仅对 机器人周围的局部区域进行重搜索,从而能保证算法的增量性及实时性;最后,通过仿真计算和机器人实验验 证了算法的有效性.     

基于混合策略的轮式机器入路径规划方法

快速扩展随机树方法（R RT）是解决具有非完整性约束的轮式机器人路径规划问题的一种有效途径。R RT能够在规划过程中引入机器人动力学约束,但是当环境中存在大量障碍物时,R RT算法的路径搜索效率将会降低。另一方面,R RT算法不具有最优性,限制了其在轮式机器人路径规划中的应用。针对经典R RT算法的不足,提出一种混合的路径规划策略,首先通过路径导引点扩展多树R RT结构,利用多树R RT的局部探索与合并特性快速寻找可通行的区域范围,利用启发式搜索算法在可通行区域内快速寻找动力学可行的机器人运动轨迹。仿真与实车实验表明,该方法能够快速有效地解决复杂障碍物环境下的机器人路径规划问题。     

Polynomial joint angle arm robot motion planning in complex geometrical obstacles

This paper addresses a point-to-point of an arm robot motion planning in complex geometrical obstacle. It will govern a two-layer optimization strategy utilizing sixth degree polynomial as joint angle path. At the beginning of the motion planning process, the path planning starts with the optimization objective to minimize the joint angle travelling distance under collision detection rules as constraint. After the best path has been met, the associated time will be searched with the optimization objective to minimize the total travelling time and the torque under the maximum velocity, the maximum acceleration, the maximum jerk, and the maximum torque constraints. The performance of a Genetic Algorithm (GA) and a Particle Swarm Optimization (PSO) will be investigated in searching the feasible sixth degree polynomial joint angle path and the total travelling time that gives the optimal trajectories under kinodynamic constraints. A 3-Degree-Of-Freedom (3-DOF) planar robot will be utilized to simulate the proposed scenario.     

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.     

<Emphasis Type="Italic">κ</Emphasis>-<Emphasis Type="Italic">PMP</Emphasis>: Enhancing Physics-based Motion Planners with Knowledge-Based Reasoning

Physics-based motion planning is a challenging task, since it requires the computation of the robot motions while allowing possible interactions with (some of) the obstacles in the environment. Kinodynamic motion planners equipped with a dynamic engine acting as state propagator are usually used for that purpose. The difficulties arise in the setting of the adequate forces for the interactions and because these interactions may change the pose of the manipulatable obstacles, thus either facilitating or preventing the finding of a solution path. The use of knowledge can alleviate the stated difficulties. This paper proposes the use of an enhanced state propagator composed of a dynamic engine and a low-level geometric reasoning process that is used to determine how to interact with the objects, i.e. from where and with which forces. The proposal, called κ-PMP can be used with any kinodynamic planner, thus giving rise to e.g. κ-RRT. The approach also includes a preprocessing step that infers from a semantic abstract knowledge described in terms of an ontology the manipulation knowledge required by the reasoning process. The proposed approach has been validated with several examples involving an holonomic mobile robot, a robot with differential constraints and a serial manipulator, and benchmarked using several state-of-the art kinodynamic planners. The results showed a significant difference in the power consumption with respect to simple physics-based planning, an improvement in the success rate and in the quality of the solution paths.     

基于循环寻优RRT算法的无人机航迹规划

针对快速扩展随机树（RRT）算法在无人机在线自主航迹规划中的寻优性问题,提出基于循环寻优RRT算法。将航迹长度代价约束作为启发条件引入RRT算法,可以有效地剪除搜索空间的无用节点,获得较优航迹。通过引入已规划可行航迹的航迹长度代价约束作为下一次算法运行的启发条件,采用循环迭代策略有效地剪除搜索空间的无用节点,使得算法每次运行后的航迹长度代价减小,多次运行后最终得到的航迹接近最优航迹,充分利用航迹长度代价的启发性,克服了RRT算法的缺点,同时获得了一系列不同航迹代价的可行备选航迹,在协同任务中可以根据协同到达时间进行快速选择。仿真结果表明该算法能够快速生成安全并且满足无人机动力学约束的较优航迹。     

Navigation with constraints for an autonomous mobile robot

This paper describes a navigation planning algorithm for a robot capable of autonomous navigation in a structured, partially known and dynamic environment. This algorithm is applied to a discrete workspace composed of a network of places and roads. The environment specification associates temporal constraints with any element of the network, and recharge or relocalisation possibilities with places. A mission specification associates several constraints with each navigation task (energy, time, position uncertainty and distance).

The algorithm computes an optimal path for each navigation task according to the optimization criterion and constraints. We introduce the notion of efficient path applied to a new best first search algorithm solving a multiple constraints problem. The path determination relies on a state representation adapted to deal with environment constraints. We then prove that the complexity chracteristics of our algorithm are similar to those of the A* algorithm.

The planner described in this paper has been implemented on a Spare station for a Robuter mobile platform equipped with ultra-sonic range sensors and an active stereo vision system. It was developed for the MITHRA family of autonomous surveillance robots as part of project EUREKA EU 110.     

A Time-optimal Trajectory Generation Approach with Non-uniform B-splines

This paper presents a novel optimization-based approach to compute time-optimal trajectories for robotic systems operating in an environment with the presence of obstacles under kinodynamic constraints. The proposed approach employs a modified rapid exploring random tree algorithm (RRT) to generate a geometrical sub-optimal path inside a feasible safe region. Subsequently, a trajectory is parametrized by fourth order non-uniform B-splines and is optimized along the path with respect to kinodynamic constraints by an interior point optimizer. The optimization process is performed in the safe region without any further collision checking, which is very effective in extremely confined and complex environments. Finally, the potential and efficiency of the approach is illustrated and compared with the notable RRT* algorithm in state space by numerical simulations.

     

On generating the motion of industrial robot manipulators

In this study, an intelligent search algorithm is proposed to define the path that leads to the desired position and orientation of an industrial robot׳s manipulator end effector. The search algorithm gradually approaches the desired configuration by selecting and evaluating a number of alternative robot׳s configurations. A grid of the robot׳s alternative configurations is constructed using a set of parameters which are reducing the search space to minimize the computational time. In the evaluation of the alternatives, multiple criteria are used in order for the different requirements to be fulfilled. The alternative configurations are generated with emphasis being given to the robot׳s joints that mainly affect the position of the end effector. Grid resolution and size parameters are set on the basis of the desired output. High resolution is used for a smooth path and lower for a rough estimation, by providing only a number of the intermediate points to the goal position. The path derived is a series of robot configurations. This method provides an inexperienced robot programmer with flexibility to generate automatically a robotic path that would fulfill the desired criteria without having to record intermediate points to the goal position.     

改进动态规划算法的移动机器人路径规划

针对静态栅格环境下的移动机器人全局路径规划问题,通过分析移动机器人到达目标的搜索方向和路径变化的动态特征,分别建立下降路径搜索动态规划模型和上升路径搜索动态规划模型,并依据整列元素路径值变化特点设计了两种模型交互使用的改进动态规划算法。仿真实验结果表明算法具有较好的路径规划效率,可以同时完成多个目标路径规划,且覆盖率越大的环境求解越快速。实验也表明改进动态规划算法同蚁群算法对比能够更快速有效地给出移动机器人较优通行路径。     

大规模AGV的改进时间窗路径规划

在机器人路径规划中,A*算法搜索路径时存在大量冗余节点,随着任务量增加,其搜索效率也会急剧下降,因此无法适应大规模任务下的路径规划。为此提出一种改进时间窗的有界次优A*算法用于求解大规模自动导引车（automatic guided vehicle,AGV）路径规划问题。算法使用时间启发式,并在搜索过程中采用时空搜索,规划无冲突的最优或次优路径。算法主要进行了三处改进：采用时间启发式,缩短了路径时间;采用动态时间窗算法,避免多次路径规划;优化了聚焦搜索算子,降低负反馈。通过MATLAB实验结果证明改进后的算法在进行多机器人路径规划时,能快速有效地规划出无冲突的平滑次优路径,搜索效率高,稳定性强。     

融合改进A*算法和Morphin算法的移动机器人动态路径规划

在动态未知环境下对机器人进行路径规划,传统A*算法可能出现碰撞或者路径规划失败问题。为了满足移动机器人全局路径规划最优和实时避障的需求,提出一种改进A*算法与Morphin搜索树算法相结合的动态路径规划方法。首先通过改进A*算法减少路径规划过程中关键节点的选取,在规划出一条全局较优路径的同时对路径平滑处理。然后基于移动机器人传感器采集的局部信息,利用Morphin搜索树算法对全局路径进行动态的局部规划,确保更好的全局路径的基础上,实时避开障碍物行驶到目标点。MATLAB仿真实验结果表明,提出的动态路径规划方法在时间和路径上得到提升,在优化全局路径规划的基础上修正局部路径,实现动态避障提高机器人达到目标点的效率。     

To push or not to push: on the rearrangement of movable objects bya mobile robot

We formulate and address the problem of planning a pushing manipulation by a mobile robot which tries to rearrange several movable objects in its work space. We present an algorithm which, when given a set of goal configurations, plans a pushing path to the "cheapest" goal or announces that no such path exists. Our method provides detailed manipulation plans, including any intermediate motion of the pusher while changing contact configuration with the pushed movables. Given a pushing problem, a pushing path is found using a two-phase procedure: a context sensitive back propagation of a cost function which maps the configuration space, and a gradient descent phase which builds the pushing path. Both phases are based on a dynamic neighborhood filter which constrains each step to consider only admissible neighboring configurations. This admissibility mechanism provides a primary tool for expressing the special characteristics of the pushing manipulation. It also allows for a full integration of any geometrical constraints imposed by the pushing robot, the pushed movables and the environment. We prove optimality and completeness of our algorithm and give some experimental results in different scenarios.     

基于栅格法的机器人路径规划蚁群算法

描述了一种静态环境下的机器人路径规划仿生算法．该算法用栅格法对场景进行建模,模拟蚂蚁的觅食行为,由多只蚂蚁协作完成最优路径的搜索．搜索过程采用了概率搜索策略、最近邻居策略和目标导引函数,使得搜索过程极为迅速高效．仿真实验结果表明,即使在障碍物非常复杂的地理环境,用本算法也能迅速规划出最优路径,且能进行实时规划,效果十分令人满意．     

基于双粒子群算法的矿井搜救机器人路径规划

针对在复杂地形中标准的粒子群算法用于矿井搜救机器人路径规划存在迭代速度慢和求解精度低的问题,提出了一种基于双粒子群算法的矿井搜救机器人路径规划方法。首先将障碍物膨胀化处理为规则化多边形,以此建立环境模型,再以改进双粒子群算法作为路径寻优算法,当传感器检测到搜救机器人正前方一定距离内有障碍物时,开始运行双改进粒子群算法:改进学习因子的粒子群算法(CPSO)粒子步长大,适用于相对开阔地带寻找路径,而添加动态速度权重的粒子群算法(PPSO)粒子步长小,擅长在障碍物形状复杂多变地带寻找路径;然后评估2种粒子群算法得到的路径是否符合避障条件,若均符合避障条件,则选取最短路径作为最终路径;最后得到矿井搜救机器人在整个路况模型中的最优行驶路径。仿真结果表明,通过改进学习因子和添加动态速度权重提高了粒子群算法的收敛速度,降低了最优解波动幅度,改进的双粒子群算法能够与路径规划模型有效结合,在复杂路段能够寻找到最优路径,提高了路径规划成功率,缩短了路径长度。     

Generating optimized paths for motion planning

This paper addresses the optimization of paths generated using randomized algorithms. We shall present an iterative algorithm to optimize raw paths. However, unlike local post-processing optimizers, our method aims at a more global optimization of the initial path, if possible, performing a drastic topological update, but instead of re-planning in the whole robot configuration space (C), it uses the initial path to limit the search within an optimal subset of C. Should a better solution be found, the subspace is further reduced. A lazy A^∗ search is used to efficiently search the graph representing the optimal subspace connectivity. The algorithm is designed to achieve a satisfactory and general optimization, while remaining computationally attractive. This paper also exposes some of the issues associated with shortcuts-like post-processing algorithms, namely, the problem of local shortcuts and their effect on the final solution. In order to assess the performance of this iterative re-planning algorithm, it is compared to the well established random shortcuts technique. Extensive experimental results are provided, these include different optimization criteria, a variety of robotic systems and environments, and different statistical measures.     

基于BIM的地图构建与导航研究

摘要: 为了提高移动机器人在作业过程中获得现场环境地图的效率,提出了利用BIM技术建立导航地图的方式,获取IFC信息映射到二维栅格,从而快速构建地图。对于室内移动机器人在移动过程中能更快更好的到达目标点的问题,首先对传统A*算法做改进,将原有的8邻域搜索扩展为48邻域搜索,增加了搜索方向,优化了搜索角度。同时考虑了机器人的安全性,对规划路径进行了改进,使得规划的路径与障碍物保持了一定距离。其次,为了避开场地出现的动态障碍物,采用将改进的A*算法与动态窗口法融合,在保证全局路径最优的基础上,实现避障效果。通过实验仿真,表明了改进的A*算法比传统A*的算法在运行时间上快了2倍以上,路径转折点的角度差比原来减少了28%以上,路径长度上更短且不再紧贴障碍物。而融合算法比改进的A*算法在路径平滑性上有所提高,能及时避开随机障碍物,更加适用于环境变化的室内场景。     

一种基于改进冲突搜索的多机器人路径规划算法

针对智能仓储环境下多载位自主移动机器人集群拣选-配送路径规划问题,提出一种改进型基于冲突搜索的多智能体路径规划算法.在模型方面,采用多载位机器人替代KIVA机器人,建立以最小化拣选-配送时间以及无效路径比为目标的数学规划模型.在算法方面,首先,提出一种基于优先级规则的多智能体冲突消解加速策略;然后,设计基于动态规划的单机器人拣选序列优化算法;最后,设计考虑转向惩罚的增强A*算法搜索机器人最优路径.实验结果表明:所提出模型与KIVA系统相比有较大优越性;所提出算法能够有效缩短拣选-配送时间、减少无效路径时间.     

基于方向约束的A*算法

实际机器人路径规划问题经常需要考虑路径的转弯约束以及路径起始/目标角要求,为此提出一种基于方向约束的A*算法.新算法区分同一路径点处不同方向的各条路径,通过定向扩展机制来满足路径方向约束,并采用节点合并策略和不一致队列降低算法复杂度.理论分析和典型地图集上的实验结果证明,所提算法总是能够保证给出符合转弯约束和起始/目标角约束的最短路径,且相比于现有算法,能够有效提高方向约束路径规划问题的求解能力.