REACTIVE MOTION PLANNING: A MULTIAGENT APPROACHLARS OVERGAARD, HENRIK G. PETERSEN, andJOHN W. PERRAMLindù Center for Applied Mathematics, OdenseUniversity, DenmarkWe present an efficient approach to reactive robot motion planning and collision avoidance.Unlike the traditional methods, there is no centralized control; instead the links and the joints of the robot are autonomous agents. This is a completely new approach. A set of dynamic equa-tions of motion for an arbitrary robot is derived. Artificial forces are introduced to express and combine multiple, possibly conflicting objectives, such as avoiding obstacles while approach-ing a goal. The joint agents impose forces of constraint between the link agents, and these forces establish a flow of information among the agents. The emergent behavior of the multi-agent system gives an impression of surprisingly intelligent overall control. The developed method is used in actual industrial applications to control welding robot installations for ship building with up to 11 degrees of freedom (DOF). Experimental results from the simulation of a 25-DOF snakelike robot operating in a complex three-dimensional structure are given. It isdemonstrated that the time complexity is O(n 3) for branched n-DOF robots, while for serialrobots such as standard manipulators and the snake, it is O(n).Robot motion planning is the problem of finding a collision-free path for a robot with internal degrees of freedom in an environment with obstacles. It is a key component in autonom ous and intelligent robot systems, where robots are instructed in which problem to solve, rather than how to solve it.Motion planning has received much attention in the last 20 years by very different approaches. Some of the most important achievements are as follows.·theoretical work on the piano movers’ problem by Schwartz and Sharir (1983)·Donald’s (1987) complete algorithm for the full 6 DOF discretized movers’problem·path planning in the robot’s configuration space (C space), suggested by Lozano-Per…z (1981, 1983, 1987)·Brooks’ (1983a, 1983b ) development of Freeways and C space techniques ·the concept of artificial potentials presented by Krogh (1984) and Khatib (1986)·Barraquand and Latombe’s (1991) work on potential functions in a hierarchicalgrid representation of the robot work spaceApplied Artificial Intelligence, 10:35±51, 1996Copyright 1996 Taylor & Francis0883-9514/96 $10.00 + .0035Lars Overgaard was supported by the Danish Research Academy and Odense Steel Shipyard Ltd.Address correspondence to Lars Overgaard, Lindù Center for Applied Mathematics, Odense University,DK-5230 Odense M, Denmark.36 L. Overgaard et al.This article presents an approach to robot motion planning inspired by the artificial potential idea and the methods for obtaining dynamic equations of motion for mechanical systems presented by Perram and Petersen (1988a) and de Leeuw et al. (1990). Artificial potential methods use artificial forces to produce the motion of a dynamic model of the robot. The forces are chosen such that they encourage the robot to do what it is supposed to do and discourages it from doing what it should not do. Kearney (1992) combined the multiple objectives of prey and predator agents, such as fear, hunger, and thirst, in a similar way. The total sum of the forces is a comprom ise of all the various, sometimes conflicting, objectives of the robot. For example, the avoidance of one obstacle might bring the robot closer to another obstacle.One of the most important advantages of the artificial potential approach over the more traditional path planning methods is that it allows reactive robot behavior toward, e.g., unexpected events in the environm ent or other robots.The basic idea of our method is to distribute control of the robot to a set of agents. Each agent is part of a constrained dynam ical system. An agent controls a subpart of the robot, and an apparently intelligent motion emerges from the agents’s rather simple attempts to selfish utility optimization. Using this distribution scheme, a very general method is obtained. That is, the complicated control of an articulated robot is reduced to a much simpler control of each subpart, and when applying the method to robots with different topologies of the parts, the only change needed is to set up the proper communication scheme among the agents.Thus our method can easily be applied to a wide range of problem s, including all combinations of off-line robot program ming, robot systems with uncertainty, on-line control of sensor-based robots, highly redundant robots, multitool robots, and multirobot systems. For simplicity, however, we concentrate on a single robot in a static well-known three-dimensional environment.The presented algorithm is incomplete. That is, it may fail to find a solution to a motion planning problem, even if a solution exists. Nevertheless, numerous experiments and actual industrial application have shown that such failures are very rare.The following section describes the multiagent model we implement to achieve reactive robot motion planning. We then describe the various agents in the multi-agent system in detail and we finally report some interesting results of applying our method to various problems.The work described in this article is part of the autonomous multiple robot operation in structured environm ents (AMROSE) project, a joint research project between Odense University and Odense Steel Shipyard Ltd. The purpose of this project is to make a system able to control multilink robots of different types working together in a complex environm ent. A more detailed description of AMROSE is found in the works by Jacobsen et al. (1990) and Larsen et al. (1991).Reactive Motion Planning 37 MULTIAGENT MOTION PLANNINGIn this section we specify the exact properties that we require from the motion planning method. The required properties lead us to identify the agents needed for the robot motion planning.Requirements to Motion PlanningThere are several requirements when planning the collision-free motion of an articulated robot. We will consider four basic requirements. It is required that the robot does not collide with objects in the environm ent and that the robot’s joints stay inside their legal range. These requirements are expressed more form ally by the following collision avoidance inequality constraints:1. The minimum distance between any link of the robot and any object in the environment must always be greater than zero.2. The value of any joint coordinate must always stay within its mechanical limits.In addition to avoiding collisions, the robot must perform some task. This is expressed through the following requirements to the end effector:3. It must reach a location at the beginning of the task.4. It must perform a specific high-precision motion from that location.We focus on these four basic requirements, although the presented m ethod can handle many other useful requirem ents. These include avoidance of collisions between different links in the same robot or between multiple robots, occlusion avoidance in vision-based robot systems, and limits on joint velocities and accelerations.The four requirements are constraints on the motion of the robot and must be taken into account during motion planning. Examples of distributed artificial intel-ligence and multiagent system approaches to constraint satisfaction in planning problem s are found in the works by Nagao and Hasida (1993) and Liu and Sycara (1993). For many problems, however, approaches outside the dom ain of traditional symbolic reasoning AI give good results. This article presents an example. Identifying the AgentsThe requirements described in the previous section lead us to view an articulated robot as a multiagent system. We identify four types of agents for the robot (see Figure 1):1. Each individual link of the robot is a self-contained link agent L with the aim of avoiding collisions with the environment.2. The aim of the joint agents J is to connect one link agent to another link agent (or to a task agent; agent type 4 below) and to avoid joint limit violations.3. End effector agents are special link agents L* with additional aims related to task perform ance.4. The high-precision task perform ance is taken care of by task agents T.This choice is a one-to-one reflection of the requirements stated in the previous section. Link agents seek to satisfy requirement 1, while joint agents take care of requirem ent 2. The end effector agents’ additional aims are to reach a location at the beginning of the task (requirement 3), and task agents force end effectors to perform high-precision motion (requirement 4). Notice that the link agents have an actual embodiment, while the joint and task agents are nonphy sical.Path FindingThe agents only respond to their local neighborhood. Therefore this method alone will not solve mazelike path finding problems of global character. We thus rely on assistance from a simple method that makes a kind of rough path findingFigure 1. The agents that control the robot are link agents L, joint agents J , and task agents T.The link agents have a physical representation; the other agents are artificial. The link and joint agents involved in task execution are marked with an asterisk.38 L. Overgaard etal.Reactive Motion Planning 39 and decomposes the global problem into a sequence of smaller motion planning problem s of local character.This ªpath finderº may be viewed as yet another agent with a global but rough view of the environm ent. The role of the path finder is to identify key points on the way to the goal and to communicate these key points to the end effector agent. Our method for local motion planning produc es the actual collision-free motion from one key point to the next.We will, however, not discuss the path finder in this article but will simply assume that it provide s the end effector agent with the necessary inform ation. More details about the path finder are given by Jacobsen et al. (1992).AGENT TYPESIn this section we describe the various types of agents in the robot motion planning method. This is the first presentation ever of this agent-based problem decomposition.Link AgentA link agent is responsible for avoiding collisions between one of the robot’s links and possible obstacles in its neighborhood. The link agent is the only type of agent that has a physical representation.Relating to the WorldThe agent must relate the link to the obstacles in the environment. In a computer simulation, the agent perform s the necessary geometric calculations based on a geometric (NURBS or polyhedron) model of the environm ent and the robot link. The closest points of the link and the environment are calculated, and the agent applies repulsive forces to the link acting in that point. The repulsive force expresses the link agent’s intention to avoid the closest obstacle point.According to Brooks (1991, p. 583), however, ªThe world is its own best model.º In systems with the proper sensors, the world model can be omitted. If the sensors provide inform ation about the required closest points, the environment model is not necessary.Choosing the Coordinate RepresentationTraditionally, a robot’s configuration is given in C space, where each dimension represents a joint coordinate. The structure of the obstacles and the description of the robot’s task, however, are given in three-dimensional Cartesian space. In order to relate the robot to the obstacles, it is necessary to either transform the robot’s configuration into Cartesian coordinates, or to transform the obstacles into C obstacles. Transformations of this kind are the main computational burden of many motion planning methods.We choose to represent the configuration of the i th link agent L i in Cartesian space by a vector r i , giving the position of the center of mass, and the three principal axis vectors u i 1, u i 2, u i 3. In this way, we remove the need for transformations to and from C space.ConstraintsThe 12 Cartesian coordinates in [r i , u i 1, u i 2, u i 3] are, of course, a redundant representation of the link’s 6 DOF. But principal axis vectors must be orthogonal unit vectors, and the redundancy is removed by the 6 constraints of orthonormality {presented by Perram and Petersen (1988b)}:u ie u if ± ef = 0 1 e f 3where ef is the Kronecker delta function.The constraints cause constraint forces to act on the dynamical system. A classic example of a system with constraint forces is the pendulum. The constraint is the constant length of the string, and the constraint force is the string force. The constraint force acts along the string and always has exactly the size necessary to keep the pendulum on a sphere with the center in the pendulum’s point of support.Likewise, each constraint on the link agents’ coordina tes causes constraint forces in the direction of the constraint.Equation of MotionFor the i th link agent L i , let q i = [r i , u i 1, u i 2, u i 3] be the vector of all the agent’s coordinates. The total force acting on the agent’s coordinates f, is the sum of theagent’s own intention forces f i and the constraint forces f c . These constraint forcesare found by solving a system of linear equations. The detailed procedure for this is described by de Leeuw et al. (1990).From the forces, we obtain the Newtonian equations of motion for the con-strained link agent coordinates:q .. = M ±1 (f i + f c )(1)where M is the diagonal mass matrix and q ..is the acceleration vector.Numerical integration of all the equations of motion will give us the motion of the multiagent system. Standard methods for num erical integration of differential equations can be found in the work by Press et al. (1988).Joint AgentThe responsibility of the joint agent is to ensure that its two link agents move as if they are connected by a mechanical joint and to ensure that the links do not violate the mechanical joint limits.40 L. Overgaard et al.The joint connection can be described by a set of geom etric constraints similar to the constraints described in the previous section. Without constraints, the two link agents have 6 DOF relative to each other. The joint agent limits this freedom to the 1 DOF of a revolute or prismatic joint by imposing five independent geometric constraints that relate [r i , u ie ] and [r j , u je ], the coordinates of the two joined agents.The constraints remove the redundancy of the Cartesian description of the system.The geometric constraints used to obtain a revolute joint are demands for constant distances between pairs of points fixed in the two links. If the points are chosen as shown in Figure 2, the only remaining freedom is rotation about the axis through the points p ij,0 and p ji,0. Let d ij,m be the distance between the two points p ij,m and p ji,0. Then the five constraints can be expressed asd ij,m ± l ij,m = 0 m = 0, 1, 2(2)d ij,m ± l ji,m = 0 m = 1, 2where the l ij,m are constants. This description of revolute joints has been given by Perram and Petersen (1988a).Something similar is done to obtain a prismatic joint. Now the five distances between the points must not be constant; we demand them to be equal. These four constraints leave one rotational and one translational degree of freedom. The rotation is prevented by demanding orthogonality of two vectors, one fixed in each link agent,as seen from Figure 3:Figure 2. The revolute joint agent J ij connects the link agents L i and L j by five distance constraints.Reactive Motion Planning41d ij,m ± d ij,0 = 0 m = 1, 2d ji,m ± d ij,0 = 0 m = 1, 2v ij v ji = 0Note that d ij,0 is not constant. The above constraints for prismatic joints were originally proposed by Overgaard (1991).Other types of joints are easily achieved. For example, Eq. (2) alone is a 3-DOF ball joint. On Figure 2 this corresponds to removing the two lines from p ji,1 and p ji,2to p ij,0.The link agents provide the joint agent with information about their positions,velocities, and intentions (forces). The joint agent then eventually adds an artificial joint limit repulsive force to the link agents’ forces. Furthermore, by communicating with other joint agents, the joint agents are able to find the proper forces due to the joint constraints. The constraint forces are also added to the link agents’ forces; they ensure that the joint constraints are exactly satisfied. Thus the flow of information communi-cated among the agents enables one agent to react on the intentions of any other agent in the multiagent system, e.g., repulsion on one link may cause all links to move.Summarizing, the role of a joint agent is to influence the intentions of its link agents in such a way that joint constraints and joint limits are not violated.Figure 3. A prismatic joint agent J ij connects the link agents L i and L j by five different geomet-ric constraints.42 L. Overgaard etal.Reactive Motion Planning 43End Effector AgentThe end effector is a link agent with additional aims. It has two different modes of behavior. During transfer movement between tasks, the end effector agent is aimed at reaching the starting point of the next task. To achieve this aim, the agent adds an attractive force directed toward the starting point.During task execution, the agent is a normal link agent without additional aims.A joint agent connects the end effector to a task agent, which guides the end effector along the task (see below).Task AgentThe task of welding, and most other tasks, requires high precision, more than can be achieved by using artificial forces. We obtain the required high-precision motion by introducing an imaginary task agent. The task agent is a moving frame of reference without any physical representation. The role of the task agent is to guide the end effector (which is passive during task execution) to execute the task.At the beginning of the task, a joint agent attaches the end effector to the task agent. W hen the task agent moves along the curve prescribed by the task specifica-tion, the joint agent forces the end effector to come along. The joint agent only imposes the constraints necessary for the specific task; the remaining freedom is left for the end effector agent.The process of welding norm ally requires control of only 5 out of the end effector’s 6 DOF; there is rotational symmetry about the torch. Therefore the end effector agent and the task agent are joined by a revolute joint about the torch.Details of the methods used to move the task agent can be found in the work by Larsen et al. (1994).EXPERIMENTAL RESULTSIn all applications, we place a level of centralized control on top of the described method. This level of control may be seen as a controller, giving input to the multiagent system. The controller assigns new tasks to end effector agents when they are ready for it. This approach has been shown to work well in several different cases.Welding ITo demonstrate the multiagent properties of our method as clearly as possible, we first show the very unusua l robot movem ent in the absence of the joint agents that norm ally connect the link agents. The link agents detect each other’s presence and react on it, but there is no other communication among the agents. Their actions44 L. Overgaard et al.are completely uncoordinated. The system’s behavior is governe d purely by the links’ selfish utility optimization.We consider a simple case, where a 5-DOF Hirobo WR-L80 robot, attached to a 3-DOF Cartesian gantry, welds two seams in a ship section. We include gravity in the artificial forces, so that all link agents tend to fall down toward the steel plates of the ship section. The link agents will try to avoid collisions with the steel plates. Furthermore, in this section’s experiment, the link agents avoid each other. Two weld tasks are assigned to the end effector.Figure 4 shows snapshots from the result of a num erical simulation of the multiagent system. The pictures show various stages of the scenery:1. The robot is in its initial configuration, and all velocities are zero.2. The robot disintegrates because of the link agents’ mutual repulsion. Because of gravity, the agents fall down toward the steel construction. The end effector falls faster than the other agents because of its additional attraction toward the corner.3. The end effector is close to the start of the first seam. At about the same time, the link agents stop falling because of their repulsion away from the steel plates.4. The end effector is attached to the task agent by a task joint agent, and the end effector starts to weld. The other agents float at safe distances from the steel plates and each other.5. The end effector has been released from the task agent and is now attracted toward another task starting in the opposite corner. During this process, a link agent is pushed away. In turn, this link agent pushes away other link agents.6. Finally, the end effector starts welding the second seam while being joined to the task agent. The link agents are repelled further away, to make more room for the end effector.This clearly demonstrates the agents’ autonomy.Welding IIIn this section, we do exactly the same as in the previous section with one extension only. We include the presence of the joint agents that connect neighboring links. The joint agents convey a flow of inform ation through the multiagent system that was absent in the previous experim ent.As before, the end effector must weld the two seams starting in the corners. The gantry has 3 DOF and the robot has 5, so the gantry/robot system is in fact an 8-DOF robot. The task agent controls 5 of the end effector’s DOF, so the system is kinematically redundant. Thus it has the freedom to avoid collisions, not only during the transfer movement between tasks but also when welding.The effect of the joint agents is clearly demonstrated by the snapshots from the simulation presented in Figure 5:Figure 4. Link agents move freely to perform their individual tasks. They all avoid collisions,and the end effector agent moves to two weld tasks. During welding, a task joint agent con-nects the end effector to the task agent.Reactive Motion Planning45Figure 5. Joint agents connect the link agents. The agents’ configuration space is now reduced to the one of the physical robot. The weld tasks are the same as in Figure 2.46 L. Overgaard etal.Reactive Motion Planning 471. The robot is in the same initial configuration as previously.2. The end effector is attracted toward the corner, and all the other agents have to follow it because of the constraint forces imposed by the joint agents.3. Now the end effector has pulled the robot close to the corner where the vertical seam begins. The comprom ise between attraction and repulsion yields a collision-free path.4. A snapshot of the welding process. The collision-free path to this configu-ration has never been planned but has simply emerged.5. After finishing the first task, the end effector is released and attracted toward the start of the next task in the other corner. The end effector and thus the other agents are repelled from the steel plates on the way to the other corner.6. The end effector has started to weld the horizontal seam. The task agent controls the process but not the end effector’s rotation about the torch.A comparison of Figure 4 and Figure 5 clearly shows the effect of the joint agents on the multiagent system.Snake SimulationWe have simulated a 25-DOF snakelike robot moving through a simple maze, using exactly the same method as in the two previous sections. The snake’s nose was the (active) end effector agent, while the other (passive) link agents were pulled through the maze without collisions. Figure 6 illustrates the result of the simulation. The time complexity of the simulation is given in the following section.A branched 25-DOF robot with two end effectors has also been simulated. Our method was immediately applicable. The only change was that the controller now had to coordinate the actions of the two end effector agents.Chirikjian and Burdick (1993) report on the actual construction of a 30-DOF planar snake robot and the method applied for obstacle avoidance. Computational C omplexityWe shall in this section find the complexities in the number of agents. Our approach has two main consum ers of computing time. One is the link agent’s computation for finding the closest obstacle. This cost is proportional to the num ber of agents in the robot. In situations where the link agents avoid each other, the cost of closest obstacle computation is quadratic in the number of agents.The other time consumer is the solution of linear equations for the constraint forces f c in Eq. (1). The matrix is irregular but sparse. Solving sets of m linear equations in general has the time complexity O(m3). The equation matrix for robots with a single chain of links is block tridiagonal, so the time complexity for a linear robot with n joints reduces from O(n3) to O(n). Figure 7 shows the total computational cost in ourFigure 6. A 25-DOF snakelike robot is maneuvering in a complex three-dimensional environment.48 L. Overgaard etal.simulations of snakes with different num bers of links. Notice that it would have been much more expensive to transform the snake’s environment (Figure 6) into C obstacles in the 25-dimensional C space and subsequently search for a feasible path.Thus the time complexity for robots with n joints varies between O (n ) for robotswith a serial chain of links to O (n 3) for very complex multitool robots, the worst casetopology.Emergent Intelligence?As stated by Brady (1985, p. 79), ªSince Robotics is the field concerned with the connection of perception to action, Artificial Intelligence must have a central role in Robotics if the connection is to be intelligent.º Although not quite up to date,Brady (1985) gives a very good review of AI and robotics.The apparently intelligent behavior of the robot in the presented experiments was achieved purely by a simple artificial force strategy. It looks as if the robot’s intelligence has appeared out of nothing. However, according to Brooks (1991,p. 585), ªIntelligence is in the eye of the observer.º The seat of intelligence is hard to identify, as the impression of intelligence is produce d by the interactions of all components, including the environment.In a recent paper, Werner (1994) presents a (rather inform al) theory called the ªcomplexity conservation principle.º Without actually defining the notion of com -plexity, Werner argues that a complex goal can only be achieved if either the agents or their environment has a complexity of matching stature.Thus, if our robot is intelligent, this intelligence is contained in the force strategy,in the structure of the robot and the environment, and in the inform ation defining the task.Figure 7. The time complexity is O (n ) for a serial robot with n joints.Reactive Motion Planning4950 L. Overgaard et al.CONC LUSIONThe multiagent model allows us to solve the motion planning problem as a distributed constraint satisfaction problem, where each agent is responsible for the satisfaction of its own partition of the constraints. It enables us to replace the traditional high-level planning approach by a low-level method with distributed local reactive control.Our approach is an artificial force method, where each agent expresses its intentions through repulsive, attractive, and constraint forces. Summarizing, the key characteristics of the presented method are as follows:Flexibility: Any robot can be controlled by this m ethod. There is no fundamental limit on the number of joints in the robot, in contrast to traditional meth-ods. The role of the individual agent is unchanged if, for example, the application is changed from one robot to another with a completely different topology.Efficiency: The obtained motion is not planned; instead it emerges because of the forces. No reasoning about future states is necessary, and thus immediate response is possible in nonstatic environments like sensor-based systems, systems with moving obstacles, and multirobot systems. The method is highly efficient for robots with many (n) joints, since the time complexity is as low as O(n) for the best case and O(n3) for the worst case. This is to be compared with the nonpolynom ial complexity of most traditional methods.Elegance: The distributed control gives rise to a very smooth and elegant movement of the articulated robot. All joints in the (possibly highly redundant) robot move simultaneously, and due to the dynamic model of the robot, there are no sudden accelerations or other discontinuities in the movement. This quality has an aesthetic value and also a practical one in the motion planning for high-speed robots.We have successfully applied the method to off-line robot progra mming at Odense Steel Shipyard Ltd. Since spring 1995, the system has been used to program 9-DOF welding robot installations in actual daily production. Later that year, a 11-DOF welding system was successfully tested. The backbone of the system is the motion planning technique described in this paper.The system is currently being extended to cover robot spray painting. The only changes are the description of the tasks and the behavior of the task agents. All other components of the system are general enough to be reused without changes. The next step is to investigate the effect of sensor feedback. Some very prom ising experiments in grasping moving objects have been perform ed. In such an on-line application, the fast response to changes provided by our reactived method is crucial.In future applications we will exploit the method’s obvious advantages in on-line control of multilink robots and multirobot systems.。
