Probabilistic Road Map sampling strategies for multi-robot motion planning

This paper presents a Probabilistic Road Map (PRM) motion planning algorithm to be queried within Dynamic Robot Networks—a multi-robot coordination platform for robots operating with limited sensing and inter-robot communication.

First, the Dynamic Robot Networks (DRN) coordination platform is introduced that facilitates centralized robot coordination across ad hoc networks, allowing safe navigation in dynamic, unknown environments. As robots move about their environment, they dynamically form communication networks. Within these networks, robots can share local sensing information and coordinate the actions of all robots in the network.

Second, a fast single-query Probabilistic Road Map (PRM) to be called within the DRN platform is presented that has been augmented with new sampling strategies. Traditional PRM strategies have shown success in searching large configuration spaces. Considered here is their application to on-line, centralized, multiple mobile robot planning problems. New sampling strategies that exploit the kinematics of non-holonomic mobile robots have been developed and implemented. First, an appropriate method of selecting milestones in a PRM is identified to enable fast coverage of the configuration space. Second, a new method of generating PRM milestones is described that decreases the planning time over traditional methods. Finally, a new endgame region for multi-robot PRMs is presented that increases the likelihood of finding solutions given difficult goal configurations.

Combining the DRN platform with these new sampling strategies, on-line centralized multi-robot planning is enabled. This allows robots to navigate safely in environments that are both dynamic and unknown. Simulations and real robot experiments are presented that demonstrate: (1) speed improvements accomplished by the sampling strategies, (2) centralized robot coordination across Dynamic Robot Networks, (3) on-the-fly motion planning to avoid moving and previously unknown obstacles and (4) autonomous robot navigation towards individual goal locations.     

Conflict free coordinated path planning for multiple robots using a dynamic path modification sequence

In this paper, a practically viable approach for conflict free, coordinated motion planning of multiple robots is proposed. The presented approach is a two phase decoupled method that can provide the desired coordination among the participating robots in offline mode. In the first phase, the collision free path with respect to stationary obstacles for each robot is obtained by employing an A* algorithm. In the second phase, the coordination among multiple robots is achieved by resolving conflicts based on a path modification approach. The paths of conflicting robots are modified based on their position in a dynamically computed path modification sequence (PMS). To assess the effectiveness of the developed methodology, the coordination among robots is also achieved by different strategies such as fixed priority sequence allotment for motion of each robot, reduction in the velocities of joints of the robot, and introduction of delay in starting of each robot. The performance is assessed in terms of the length of path traversed by each robot, time taken by the robot to realize the task and computational time. The effectiveness of the proposed approach for multi-robot motion planning is demonstrated with two case studies that considered the tasks with three and four robots. The results obtained from realistic simulation of multi-robot environment demonstrate that the proposed approach assures rapid, concurrent and conflict free coordinated path planning for multiple robots.     

Adaptive dynamic collision checking for single and multiple articulated robots in complex environments

Static collision checking amounts to testing a given configuration of objects for overlaps. In contrast, the goal of dynamic checking is to determine whether all configurations along a continuous path are collision-free. While there exist effective methods for static collision detection, dynamic checking still lacks methods that are both reliable and efficient. A common approach is to sample paths at some fixed, prespecified resolution and statically test each sampled configuration. But this approach is not guaranteed to detect collision whenever one occurs, and trying to increase its reliability by refining the sampling resolution along the entire path results in slow checking. This paper introduces a new method for testing path segments in c-space or collections of such segments, that is both reliable and efficient. This method locally adjusts the sampling resolution by comparing lower bounds on distances between objects in relative motion with upper bounds on lengths of curves traced by points of these moving objects. Several additional techniques and heuristics increase the checker's efficiency in scenarios with many moving objects (e.g., articulated arms and/or multiple robots) and high geometric complexity. The new method is general, but particularly well suited for use in probabilistic roadmap (PRM) planners, where it is critical to determine as quickly as possible whether given path segments collide, or not. Extensive tests, in particular on randomly generated path segments and on multisegment paths produced by PRM planners, show that the new method compares favorably with a fixed-resolution approach at "suitable" resolution, with the enormous advantage that it never fails to detect collision.     

能耗优化下的多移动机器人动态避撞机制

针对多移动机器人在停车避撞时能耗优化的问题,提出能耗优化下基于滚动时间窗和二叉树先序遍历的多移动机器人动态避撞(TW & BT)融合算法。基于改进A^*算法求得能耗约束下的最优初始路径。依据滚动时间窗和二叉树先序遍历协同机制,以初始路径中移动机器人碰撞为触发事件,将整个作业时间轴分解为多个时间窗;在每个时间窗,以停车避撞时产生能耗最小为目标,基于二叉树先序遍历的算法求解最优避撞决策。仿真实验结果表明,一方面TW & BT融合算法具有较高的鲁棒性;另一方面对比基于动态优先级的冲突消解策略(DPS)方法,在相近的计算时间内,TW & BT融合算法实现避撞时产生能耗降低达33.1％。     

Safe and efficient motion planning of multiple mobile robots based on artificial potential for human behavior and robot congestion

In order for robots to exist together with humans, safety for the humans has to be strictly ensured. On the other hand, safety might decrease working efficiency of robots. Namely, this is a trade-off problem between human safety and robot efficiency in a field of human–robot interaction. For this problem, we propose a novel motion planning technique of multiple mobile robots. Two artificial potentials are presented for generating repulsive force. The first potential is provided for humans. The von Mises distribution is used to consider the behavioral property of humans. The second potential is provided for the robots. The Kernel density estimation is used to consider the global robot congestion. Through simulation experiments, the effectiveness of the behavior and congestion potentials of the motion planning technique for human safety and robot efficiency is discussed. Moreover, a sensing system for humans in a real environment is developed. From experimental results, the significance of the behavior potential based on the actual humans is discussed. For the coexistence of humans and robots, it is important to evaluate a mutual influence between them. For this purpose, a virtual space is built using projection mapping. Finally, the effectiveness of the motion planning technique for the human–robot interaction is discussed from the point of view of not only robots but also humans.     

未知环境下分布式多机器人避碰协作算法

针对多机器人协作问题,提出一种未知环境下分布式多机器人协作避碰算法。该算法基于分布式投标模型协调多机器人运动,改进过去算法的前提假设,综合考虑机器人的实际尺寸和传感误差,通过自适应设定投标时间,提高算法的效率,针对通信延时引起的信息不一致,采用按优先级顺序进行探测的方法。仿真实验验证了该算法的可行性。     

A decentralized approach for the conflict-free motion of multiple mobile robots

This article presents a novel approach to decentralized motion planning and conflict-resolution for multiple mobile robots. The proposed multi-robot motion planning is an on-line operation, based on cost wave propagation within a discretized configuration space-time. By use of the planning method, a framework for negotiation is developed, which permits quick decentralized and parallel decision making. The key objective of the negotiation procedure is dynamic assignment of robot motion priorities. Thus, robots involved in a local conflict situation cooperate in planning and execution of the lowest cost motion paths without application of any centralized components. The features required for individual and cooperative motion are embedded in a hybrid control architecture. Results obtained from realistic simulation of a multi-robot environment and also from experiments performed with two mobile robots demonstrate the flexibility and the efficiency of the proposed method.     

Practical Point-to-Point Multiple-Goal Task Realization in a Robot Arm with a Rotating Table

This study presents a multiple-goal task realization in a system composed of a 6-d.o.f. robot arm and a one-axis rotating table. The problem is complex due to the existence of multiple goals and the kinematic redundancy of the system. We propose a design approach integrating the base placement, task sequencing and motion coordination methods. We show that this approach reduces the task completion time of the robot arm; the motion planning is realized through straight-line paths in the configuration space despite collision occurrences. Furthermore, we introduce a hybrid graph-search method combining the greedy nearest-neighbor method and the Dijkstra method to solve the motion coordination of the robot arm and the table. We show the effectiveness of the design approach and the search method through a time-constrained simulation-based optimization.     

Optimal assignment of robot tasks with precedence for muliti-robot coordination by disjunctive graphs and state-space search

An approach to optimal assignment of tasks with precedence relationships to multiple robots is proposed. The robots are assumed to share a common workspace and work cooperatively to accomplish a given process plan consisting of a set of tasks. The optimal task assignment is defined to be the one that results in spending the least amount of time to complete the plan under the criterion that no robot collision will occur when the assigned tasks are performed. The ordering of the tasks in the process plan is described by a topological tree, which is then expanded to form a larger state-space tree without redundant tree paths. Each path in the expanded tree represents a partially developed assignment of the tasks to the robots, and a graph formulation scheme is presented for estimating the cost of the assignment. A collision-free motion schedule for each robot based on each task assignment can be obtained by finding the minimaximal path in a disjunctive graph formulated by the scheme. By using the A^* algorithm, a search method for finding the optimal assignment with the minimum cost is presented. Some heuristic rules are also proposed to speed up the search process. Simulation results are illustrated to show the effectiveness of the proposed approach. © 1995 John Wiley & Sons, Inc.     

基于改进人工势场法的机器人动态追踪与避障

针对移动机器人对动态目标的追踪和对拦截型障碍物的避障问题,将势场法进行改进,提出了辅助斥力环方法,改变了传统势场法中斥力的作用方式和机器人的避障策略,使其在动态环境下处理避障问题更加灵活有效.仿真研究验证了此方法的有效性.     

Real-time Velocity Alteration Strategy for Collision-free Trajectory Planning of Two Articulated Robot Manipulators

Two articulated robots working in a shared workspace can be programmed by planning the tip trajectory of each robot independently. To account for collision avoidance between links, a real-time velocity alteration strategy based on fast and accurate collision detection is proposed in this paper to determine the step of next motion of slave (low priority) robot for collision-free trajectory planning of two robots with priorities. The effectiveness of the method depends largely on a newly developed method of accurate estimate of distance between links. By using the enclosing and enclosed ellipsoids representations of polyhedral models of links of robots, the minimum distance estimate and collision detection between the links can be performed more efficiently and accurately. The proposed strategy is implemented in an environment where the geometric paths of robots are pre-planned and the preprogrammed velocities are piecewise constant but adjustable. Under the control of the proposed strategy, the master robot always moves at a constant speed. The slave robot moves at the selected velocity, selected by a tradeoff between collision trend index and velocity reduction in one collision checking time, to keep moving as far as possible and as fast as possible while avoid possible collisions along the path. The collision trend index is a fusion of distance and relative velocity between links of two robots to reflect the possibility of collision at present and in the future. Graphic simulations of two PUMA560 robot arms working in common workspace but with independent goals are conducted. Simulations demonstrate the collision avoidance capability of the proposed approach as compared to the approach based on bounding volumes. It shows that advantage of our approach is less number of speed alterations required to react to potential collisions.     

Navigating Multiple Mobile Robots without Direct Communication

A bulk of research is being done for the autonomous navigation of a mobile robot. Multirobot motion planning techniques often assume a direct communication among the robots, which makes them practically unusable. Similarly, approaches assuming the robot moving amid humans assume cooperation of humans, which may not be the case if the human is replaced by a robot. In this paper, a deliberative planning at the higher level with a new cell decomposition technique is presented, along with a reactive planning technique at the finer level, which uses fuzzy logic. Coordination among the robots in the absence of direct communication and knowledge of other robot's intent is a complex research question, which is solved using a simple fuzzy‐based modeling. Experimental results show that the multiple robots maintain comfortable distances from the obstacles, navigate by near optimal paths, can easily escape previously unseen obstacles, and coordinate with each other to avoid collision as well as maintain a large separation. This work displays a simple and easy to interpret system for solving complex coordination problem in multirobotics.     

Real-time safety for human–robot interaction

This paper presents a strategy for ensuring safety during human–robot interaction in real time. A measure of danger during the interaction is explicitly computed, based on factors affecting the impact force during a potential collision between the human and the robot. This danger index is then used as an input to real-time trajectory generation when the index exceeds a predefined threshold. The danger index is formulated to produce a provably stable, fast response in the presence of multiple surrounding obstacles. A motion strategy to minimize the danger index is developed for articulated multi-degree-of-freedom robots. Simulations and experiments show the efficacy of this approach.     

Distance-based Formation Control Using Angular Information Between Robots

Distance-based formation of groups of mobile robots provides an alternative focus for motion coordination strategies respect to the standard consensus-based formation strategies. However, the setup formulation introduces non rigidity problems, multiple formation patterns that verify the distance constraints or local minima appeared when collision avoidance strategies are added to the control laws. This paper proposes a novel combined distance-based potential functions with attractive-repulsive behavior in order to simplify the navigation problem as well as the use of angular information between robots to reduce the likelihood of unwanted formation patterns. Moreover, this approach eliminates the local minima generated by the control laws to reach the desired formation configuration in the case of three robots. The analysis addresses the case of omnidirectional robots and is extended to the case of unicycle-type robots with numerical simulations and real-time experiments.     

Autonomous multi-mobile robot system: simulation and implementation using fuzzy logic

In an autonomous multi-mobile robot environment, path planning and collision avoidance are important functions used to perform a given task collaboratively and cooperatively. This study considers these important and challenging problems. The proposed approach is based on a potential field method and fuzzy logic system. First, a global path planner selects the paths of the robots that minimize the potential value from each robot to its own target using a potential field. Then, a local path planner modifies the path and orientation from the global planner to avoid collisions with static and dynamic obstacles using a fuzzy logic system. In this paper, each robot independently selects its destination and considers other robots as dynamic obstacles, and there is no need to predict the motion of obstacles. This process continues until the corresponding target of each robot is found. To test this method, an autonomous multi-mobile robot simulator (AMMRS) is developed, and both simulation-based and experimental results are given. The results show that the path planning and collision avoidance strategies are effective and useful for multi-mobile robot systems.     

基于人工协调场的多移动机器人实时协调避碰规划

为克服传统人工势场在动态未知环境下机器人避碰规划中存在的缺陷,提出人工协调场法(ACF).将场函数与机器人的风险状态相结合,给出并讨论了人工协调场的基本设计.基于人工协调场,考虑机器人的运动约束,实现了多机器人之间以及机器人与环境间的实时协调避碰,提出了一个多移动机器人无死锁实时避碰规划算法.理论分析和仿真试验证明所提方法的有效性.     

A Case Study of the Collision-Avoidance Problem Based on Bernstein–Bézier Path Tracking for Multiple Robots with Known Constraints

In this paper a case study of a new, cooperative, collision-avoidance method for multiple, nonholonomic robots based on Bernstein–Bézier curves is given. In the presented examples the velocities and accelerations of the mobile robots are constrained and the start and the goal velocity are defined for each robot. This means that the proposed method can be used as a subroutine in a huge path-planning problem in real time, in a way to split the whole path into smaller partial paths. The reference path of each robot, from the start pose to the goal pose, is obtained by minimizing the penalty function, which takes into account the sum of all the path lengths subjected to the distances between the robots, which should be bigger than the minimum distance defined as the safety distance, and subjected to the velocities and accelerations which should be lower than the maximum allowed for each robot. When the reference paths are defined the model-predictive trajectory tracking is used to define the control. The prediction model derived from the linearized tracking-error dynamics is used to predict future system behavior. The control law is derived from a quadratic cost function consisting of the system tracking error and the control effort. The proposed method was tested with a simulation and with a real-time experiment in which four robots were used.     

Cooperative collision avoidance between multiple mobile robots

This paper presents a new collision avoidance technique, called cooperative collision avoidance, for multiple mobile robots. The detection of the danger of collision between two mobile robots is discussed with respect to the geometric aspects of their paths as are cooperative collision avoidance behaviors. The direction control command and the velocity control command for the cooperative collision avoidance are then proposed. The avoidance technique is extended to cases in which the number of mobile robots is more than two. Furthermore, the conditions for collision avoidance are considered with respect to the navigation parameters and guidelines of designing the navigation parameters are obtained. The effectiveness of the proposed technique is demonstrated by means of numerical simulation and navigation experiments using two real mobile robots named Pioneer‐1. ©2000 John Wiley & Sons, Inc.     

A dynamic priority based path planning for cooperation of multiple mobile robots in formation forming

Robots that work in a proper formation show several advantages compared to a single complex robot, such as a reduced cost, robustness, efficiency and improved performance. Existing researches focused on the method of keeping the formation shape during the motion, but usually neglect collision constraints or assume a simplified model of obstacles. This paper investigates the path planning of forming a target robot formation in a clutter environment containing unknown obstacles. The contribution lies in proposing an efficient path planner for the multiple mobile robots to achieve their goals through the clutter environment and developing a dynamic priority strategy for cooperation of robots in forming the target formation. A multirobot system is set up to verify the proposed method of robot path planning. Simulations and experiments results demonstrate that the proposed method can successfully address the collision avoidance problem as well as the formation forming problem.     

Collision Avoidance by Using Space-Time Representations of Motion Processes

This paper handles the problem of collision avoidance in a multi-robot environment. To solve this problem, the motion processes of the mobile robots are modelled in space-time. Since the robots are autonomous and communication is non-deterministic, there is temporal uncertainty in addition to spatial uncertainty. The paper presents a method to model both uncertainty components in a homogeneous way. It is shown, that it is not sufficient to guarantee a spatial security distance between the robots. Distances in space-time and space-time vectors must be considered. The main result of this paper is a straightforward and efficient solution to the problem of collision avoidance between up to three mobile robots by applying a space-time displacement vector. The solution is based on space-time, which is a helpful view onto our world in relativity theory and quantum physics. Space-time methods are also very valuable in Robotics, especially for problems in dynamic environments and for motion coordination of mobile robots. Practical experiments with up to two robots, and simulations of up to three robots have been performed and are reported.