VCS-based motion planning for distributed mobile robots: collision avoidance and formation

This paper addresses decentralized motion planning among a homogeneous set of feedback-controlled mobile robots. It introduces the velocity obstacle, which describes the collision between robot and obstacle, and the hybrid interactive velocity obstacles are designed for collision checking between interacting robots. The (sub)goal selection algorithm is also studied for formation control, then the preferred velocity is designed for robot tracking its desired (sub)goal. Furthermore, the rules for the size regulation of obstacle are presented to avoid conservative motion planning and enhance the safety. Then, we establish a novel Velocity Change Space (VCS), map the velocity obstacles, the desired (sub)goal and the reachable velocity change window before collision in this space, and directly get the new velocity by a multi-objective optimization method. We apply VCS-based motion planning methods to distributed robots, and simulation is used to illustrate the good performances with respect to the un-conservative, foresighted and multi-objective optimal motion planning, especially the successful application in the formation control of the multi-robot system.     

VARIABLE PATROL PLANNING OF MULTI-ROBOT SYSTEMS BY A COOPERATIVE AUCTION SYSTEM

A cooperative auction system (CAS) is proposed to solve the large-scale multi-robot patrol planning problem. Each robot picks its own patrol points via the cooperative auction system and the system continuously re-auctions, based on the team work performance. The proposed method not only works in static environments but also considers variable path planning when the number of mobile robots increases or decreases during patrol. From the results of the simulation, the proposed approach demonstrates decreased time complexity, a lower routing path cost, improved balance of workload among robots, and the potential to scale to a large number of robots and is adaptive to environmental perturbations when the number of robots changes during patrol.     

Motion planning for cooperative unicycle-type mobile robots with limited sensing ranges: A distributed receding horizon approach

This paper presents a decentralized motion planner for a team of nonholonomic mobile robots subject to constraints imposed by sensors and the communication network. The motion planning scheme consists of decentralized receding horizon planners that reside on each vehicle to achieve coordination among flocking agents. The advantage of the proposed algorithm is that each vehicle only requires local knowledge of its neighboring vehicles. The main requirement for designing an optimal conflict-free trajectory in a decentralized way is that each robot does not deviate too far from its presumed trajectory designed without taking the coupling constraints into account. A comparative study between the proposed algorithm and other existing algorithms is provided in order to show the advantages, especially in terms of computing time. Finally, experiments are performed on a team of three mobile robots to demonstrate the validity of the proposed approach.     

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.     

Contribution to the path planning of a multi-robot system: centralized architecture

The current study is set to investigate the problem of planning trajectories for a multi-robot system in a dynamic environment. The planning study is conducted in a “barrier-free” and “with obstacle” environment, based on the artificial potential field (APF) technique. This study seeks to improve the APF method in order to have good trajectory planning of a multi-robot system. Also, for multi-robot mobile systems, one of the main technical considerations is the technique used to coordinate the movements of different robots. In this paper, we proposed a centralized architecture for the trajectory planning of a multi-robot system.

     

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.     

一个面向复杂任务的多机器人分布式协调系统

基于多智能体系统理论, 研究在非结构、不确定环境下面向复杂任务的多机器人分布式协调系统的实现原理、方法和技术. 提出的递阶混合式协调结构、基于网络的通讯模式和基于有限状态机的规划与控制集成方法, 充分考虑了复杂任务和真实自然环境的特点. 通过构建一个全实物的多移动机器人实验平台, 对规划、控制、传感、通讯、协调与合作的各关键技术进行了开发和集成, 使多机器人分布式协调技术的研究直接面向实际应用, 编队和物料搬运的演示实验结果展示了多机器人协调技术的广阔应用前景.     

Decentralized multi-robot encirclement of a 3D target with guaranteed collision avoidance

We present a control framework for achieving encirclement of a target moving in 3D using a multi-robot system. Three variations of a basic control strategy are proposed for different versions of the encirclement problem, and their effectiveness is formally established. An extension ensuring maintenance of a safe inter-robot distance is also discussed. The proposed framework is fully decentralized and only requires local communication among robots; in particular, each robot locally estimates all the relevant global quantities. We validate the proposed strategy through simulations on kinematic point robots and quadrotor UAVs, as well as experiments on differential-drive wheeled mobile robots.     

凸优化与A*算法结合的路径避障算法

为提高足式移动机器人的避障能力和路径规划效率,提出一种凸优化与A*算法结合的路径避障算法.首先,基于半定规划的迭代区域膨胀方法IRI-SDP(iterative regional inflation by semi-definite programming),通过交替使用两种凸优化算法快速计算出地面环境中无障碍凸多边形及其最大面积内切椭圆,用于移动机器人的局部避障和任务动作规划;然后,结合经典的A*算法,建立机器人局部和世界坐标系、机器人质心轨迹转换模型、碰撞模型和启发式代价函数,在全局环境中寻找最优成本最小的路径;最后,通过仿真实验验证该算法的有效性.     

融合路径跟踪模式的多移动机器人有序化群集运动控制

针对多移动机器人群集运动的实现及其避障问题,提出了一类融合路径跟踪模式的有序化群集运动控制算法．该算法将有leader的群集运动模式与队列运动模式相结合,实现了多机器人系统快速聚合行为与有效避障行为的统一．移动机器人群仿真实验验证了该方法的有效性．     

多移动机器人协同搬运技术综述

多移动机器人协同搬运系统是多移动机器人系统的典型应用，在一些特殊场合中具有较强的应用潜力。对此，本文综述了多移动机器人协同搬运的相关技术，总结了国内外的发展状况。针对不同的搬运对象，分析比较了抓取、推拉、锁定3种搬运方案，重点分析了不同搬运方案下的多移动机器人协同搬运策略算法原理以及各自的优缺点；概述了多移动机器人搬运系统中涉及的周边技术，主要包括多移动机器人任务分配、环境感知定位、轨迹规划3个方面；最后对多移动机器人协同搬运技术的研究方向进行了展望。     

考虑障碍环境下的多机器人编队控制研究

编队和避障控制是机器人路径规划设计中的典型问题,文中提出了将leader—following法和人工势场法相结合的方法,来更好地完成多机器人在未知环境下的编队和避障控制。之前的研究只将leader—following算法用于多机器人的编队控制,而文中提出此方法也可以用于多机器人系统的避障控制。基于leader—following法,多机器人能自动编队并保持队形;而结合人工势场法,多机器人可以保持队形行进,在遇到障碍物的情况下变换队形避障,在避障后恢复原队形,最终到达目标。通过仿真实验证明,该算法实现了多机器人在未知环境下的自动编队和避障,从而证明了leader—following算法可以用于机器人的避障控制。     

A distributed multi-agent production planning and scheduling framework for mobile robots

Inspired by the new achievements in mobile robotics having as a result mobile robots able to execute different production tasks, we consider a factory producing a set of distinct products via or with the additional help of mobile robots. This particularly flexible layout requires the definition and the solution of a complex planning and scheduling problem. In order to minimize production costs, dynamic determination of the number of robots for each production task and the individual robot allocation are needed. We propose a solution in terms of a two-level decentralized Multi-Agent System (MAS) framework: at the first, production planning level, agents are tasks which compete for robots (resources at this level); at the second, scheduling level, agents are robots which reallocate themselves among different tasks to satisfy the requests coming from the first level. An iterative auction based negotiation protocol is used at the first level while the second level solves a Multi-Robot Task Allocation (MRTA) problem through a distributed version of the Hungarian Method. A comparison of the results with a centralized approach is presented.     

一种基于情绪量的多机器人冲突消解方法

针对动态非结构化环境下多机器人之间存在的空间冲突问题,提出了一种基于情绪量的多机器人冲突消解方法。该方法可以使机器人根据情绪量自主判定对其他机器人的躲避半径,无须预先设定固定的避碰优先级或进行机器人之间的协商。仿真结果表明该方法是一种有效的多机器人冲突消解方法。     

Efficient terrain coverage for deploying wireless sensor nodes on multi-robot system

Coverage and connectivity are the two main functionalities of wireless sensor network. Stochastic node deployment or random deployment almost always cause hole in sensing coverage and cause redundant nodes in area. In the other hand precise deployment of nodes in large area is very time consuming and even impossible in hazardous environment. One of solution for this problem is using mobile robots with concern on exploration algorithm for mobile robot. In this work an autonomous deployment method for wireless sensor nodes is proposed via multi-robot system which robots are considered as node carrier. Developing an exploration algorithm based on spanning tree is the main contribution and this exploration algorithm is performing fast localization of sensor nodes in energy efficient manner. Employing multi-robot system and path planning with spanning tree algorithm is a strategy for speeding up sensor nodes deployment. A novel improvement of this technique in deployment of nodes is having obstacle avoidance mechanism without concern on shape and size of obstacle. The results show using spanning tree exploration along with multi-robot system helps to have fast deployment behind efficiency in energy.     

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.     

基于滚动优化和分散捕食者猎物模型的全覆盖路径规划算法

针对多机器人执行全覆盖任务效果差的问题,提出一种基于滚动优化和分散捕食者猎物模型的多机器人全覆盖路径规划算法.首先,利用栅格地图表示作业的环境空间,并基于栅格地图修正捕食者猎物算法中的避开捕食者奖励,添加移动代价奖励和死区回溯机制构建分散捕食者猎物模型;然后,引入滚动优化方法,避免机器人陷入局部最优,预测周期内机器人覆盖栅格的累计奖励值作为适应度函数,并使用鲸鱼优化算法(WOA)求解最优移动序列;最后,在不同环境下进行仿真实验,得到的平均路径长度与生物激励神经网络算法(BINN)和牛耕式A*算法(BA*)相比分别减少了16.69%sim17.33%、10.32%sim20.03%,验证了所提出算法在多机器人全覆盖路径规划中的可行性和有效性.     

Multi-robot spot-welding cells for car-body assembly: Design and motion planning

Multi-robot cells for spot welding use coordinated robots to assemble metal panels via spot welding by coordinated robots, for instance in the construction of car doors. The design of multi-robot cells for spot welding required both cell design and off-line motion planning. Cell design involves resource selection (such as robots and welding guns) and resource configuration, while considering cell productivity, costs, flexibility and reconfigurability. Motion planning involves allocating welding points to each resource and calculating collision-free motion plan for each robot. Currently, cell design and motion planning are sequential and manual activities, managed by different and separate industrial functional units. This results in several cycles before the design converges to a feasible final solution. The proposed approach introduces a unified methodology, aiming at optimizing the holistic cell design and motion planning, that reduces design time and errors. The feasibility of the proposed approach has been demonstrated in several ad-hoc basic replicable cases and in one industrial case. The outcome of this research improves state of the art, reducing design and motion planning time over current technology. Moreover, the method has been integrated into a computerized approach which has the potential to accelerate the whole cell design and motion planning processes and to reduce human efforts.     

Multi-robot cooperation-based mobile printer system

This paper proposes a mobile printer system (MPS) based on multi-robot cooperation. The system consists of multiple mobile robots, a wireless LAN system, a graphic user interface (GUI), and a host computer. The GUI comprises a user input section, a task allocation optimization section, and a control and communication section. Its operation is as follows: a user draws a picture on an input window of the GUI, and then the host computer commands client printer-robots to reproduce the same on a paper in a finite time.To control multiple robots during this process, two kinds of multi-robot control architectures along with a collision-free arbitration configuration are proposed. One is a decentralized control architecture, which employs subsumption architecture based on behavior-based robotics. The robots continue to seek the nearest line and to draw it repeatedly until all lines are drawn. This architecture needs no pre-planning and is fault-tolerant. Another is a centralized control architecture, which employs an evolutionary algorithm (EA). The host computer optimizes the task (finding time-optimal path) allocation for each robot by using an evolutionary algorithm and sends the optimized job sequence to the robots. To minimize the elapsed time in drawing all the lines, an evolutionary algorithm with a representation of an individual suitable for the MPS is employed for the task optimization. This architecture can minimize the elapsed time effectively and offers the option of distance-optimality in addition to time-optimality.The proposed architectures are simulated and real experiments with three omni-directional robots are carried out to demonstrate the effectiveness and the applicability of the proposed mobile printer system.