A Divide-and-Conquer Method of Path Planning for Cooperating Robots with String Tightening
Jonathan M R Weaver, Stephen J. Derby · 2005
This paper presei1.i.s a inethod for aut011 oinously planning collision free p aths for two cooperating TOhOtS in a static eiivironinent. Coopemiiirg robots szinultaiieously grasp and inaii.ipnlate a single object. Our method utilizes a divide-and-conquer type of heuristic and involves lion-exhaustive mapping of configuration space. Although the method was developed especially for the cooperating robot case, it is also applicable to the single robot path planning problem. While there is no guarantee of finding a soluiioi~., th,e algorithm has been successfully applied to a variety of problems including two cooperatiirg nine dof arnis. .4 meih od is also presented to sm.ooth a safe palh. inlo one with shorter joint space trajectories. Sam.ple results are included. The robot path planning problem involves det,ermining if a continuous and obstacle avoiding path esists between st<art and goal posit,ions, and, if so, t.o find such a path. The complexity of the pat,li planning problem has been shown to be esponentia.1 in the number of dof [l, 21. A subset of the general path planning problem is the path planning problem for tiro coopera.t.ing rob0t.s. By cooperation, it is lierein meant t.lia,t bot,Ii robot,s simultaneously grip a.nd miinipula.t.e a con~~non, rigid, payload. During cooperat,ion, t.he relat.ive position a.nd orienta.tion of the two grippers remain consthit,. One possible applica.tion for cooperat,ing robots is the assembly and maintenance of a space stat.ion. A major obstacle in implementing a coopera.ting robot,ic system is the coinplesity of the path planning problem. Although many approaches to the general single arm path planning problem have been presented in the literature, most have not considered nor appear to be easily extensible to the case of cooperathg robot arms. Many of the typical assumptions nmde in single robot planning are invalid in the coopera.t.ing robot case. Thus, there is an apparent need for improved cooperating robot path planning techniques. This paper presents a method developed for global path planning of two cooperat.ing robot. arms in a. static environment. The method is an est.ension of t.lie single arm approach present.ed by Dupont [3] whereby select,ive searching of c-space makes it possible to obta.in a solution in a reasonable amount of time. Dupont. used Cartesian heuristics to direct the select.ive mapping process. Because of the added complexity of the coopera.t.ing robot problem, a new divideand-conquer type of c-space traversal algorithm was developed to guide the selective mapping process. The c-spa.ce traversal algorithm and its application to the robot path planning problem are described herein. Resu1t.s are presented for applying the procedure to two coopera.ting six dof Pumas and two cooperating nine dof robots. The met,liod has also been successully applied to a single six dof Puma and a single nine dof puma. Because our emphasis is on the cooperating robot scenario, the single arm cases will not be discussed further herein. Once a given path planning problem has been solved [4, 51, it inay be possible to modify the path to one which is better in some sense than the original path. This process may be referred to as t.ightening [3]. A method is presented for string tightening for cooperating robots. Sa.mple results are given for string tightening a path for cooperating nine dof robots.