当前位置:首页 >> >>


Vehicle Motion Planning Using Stream Functions
Submitted as a regular paper to IEEE Transactions on Robotics and Automation

Stephen Waydo, Student Member, IEEE Control and Dynamical Systems California Institute of Technology, Mail Code 107-81 1200 E. California Blvd Pasadena, CA 91125 waydo@cds.caltech.edu fax: (626)796-8914
Abstract Borrowing a concept from hydrodynamic analysis, this paper presents stream functions which satisfy Laplace’s equation as a local-minima free method for producing potential-?eld based navigation functions in two dimensions. These functions generate smoother paths (i.e. more suited to aircraft-like vehicles) than previous methods. A method is developed for constructing analytic stream functions to produce arbitrary vehicle behaviors while avoiding obstacles, and an exact solution for the case of a single uniformly moving obstacle is presented. The effects of introducing multiple obstacles are discussed and a modi?cation of the theory to handle this case is presented. Experimental results generated on the Cornell RoboFlag testbed are presented and discussed, as well as related work applying these methods to path planning for unmanned air vehicles. Index Terms path planning, stream functions, harmonic functions, RoboFlag.

This work was supported in part by the Defense Advanced Research Projects Agency under cooperative agreement F30602-01-2-0577 and by the Fannie and John Hertz Foundation. S. Waydo is with the California Institute of Technology.



Vehicle Motion Planning Using Stream Functions
Submitted as a regular paper to IEEE Transactions on Robotics and Automation



S autonomous vehicles such as unmanned air vehicles (UAV’s) become more commonplace, it is becoming increasingly necessary to develop methods by which the vehicles assume a higher degree of autonomy. For example, such methods would allow the current ratio of four to ?ve operators for a single UAV to be inverted or better, with a few operators capable of controlling many vehicles. An experimental scenario we have chosen to explore this issue is RoboFlag [1], [2], a game akin to “Capture the Flag” in which one or two humans control a group of eight vehicles as they attempt to capture a ?ag in an opponent’s territory and return to their home base. The robots must also avoid being tagged out by an opposing team’s robot and attempt to prevent the opponent capturing their own ?ag, all while avoiding neutral obstacles. Fig. 1 depicts a global view of such a game in progress. It is clear from the situation in the ?gure that low-level control tasks such as obstacle avoidance must be automated in order for just one or two humans to successfully play the game. Furthermore, it would be very desirable for the automated behavior to be very intuitive in that the operators should not be surprised by what paths their vehicles take given the commands they have issued. The goal of the RoboFlag game is to determine what technologies will be required to enable a small number of humans to manage a large number of autonomous vehicles. One eventual application area of such technologies will be in the guidance and control of UAV’s. This goal complicates the path planning problem in that, in contrast to car-like vehicles or manipulators, aircraft exhibit nonlinear second order dynamics which impose requirements such as minimum speeds and turning radii that may not be easily satis?ed by current planning methods. One method for on-line robot path planning with obstacle avoidance is to follow the (sometimes negated) gradient of an arti?cial potential ?eld which is constructed such that the resulting vector ?eld is exterior directed on the boundaries of the con?guration space. A major challenge in constructing these ?elds is guaranteeing that a vehicle will reach the goal from any initial position, meaning that the potential ?eld has no local extrema aside from the desired goal. There is a further complication, especially apparent in such provably correct methods, that the paths produced by following the gradient of a potential function may not satisfy the second order, nonlinear dynamics of an aircraft-like vehicle. The hydrodynamic concept of a harmonic stream function may be useful with respect to both of these issues. Stream functions (and the potential functions associated with them) have no local extrema, and they generate smoother paths then many

Fig. 1. Global view of a RoboFlag game. Black vehicles, based on the left side of the ?eld, must capture ?ag (black dot) from white defense zone (large white circle) and return it to their home zone (gray quarter circle) without being tagged, while defending their own ?ag from the white team and while avoiding neutral obstacles (gray circles).

potential functions and hence better nominal paths for second order systems. Potential ?eld and stream function methods such as the one described here offer a natural way in which a human can interface with a group of vehicles. Rather than assuming direct control over vehicle behavior, a strategy that limits an operator to controlling a single vehicle at a time, the human can shape the world that the vehicles operate in by tagging various objects or locations as obstacles, goals, or other primitives. These primitives can then be (automatically) composed into a resultant ?eld which governs vehicle behavior and which expresses operator intent while allowing the vehicles to handle the low-level control tasks to which computers are particularly well suited. If the operator is temporarily taken away from the control task, the autonomous vehicles have behavioral guidelines encoded in their perceived potential ?eld that allow them to continue to behave in a desirable manner. This work is motivated by problems described in [3] and [4]. The original concept of potential-?eld navigation was due to Khatib, who summarizes his approach in [5]. Koditschek and Rimon examine the topological properties of navigation functions in [6]. Connolly and Grupen describe the application of numerical (?nite-difference) solutions of Laplace’s equation to robot navigation in [7]. Kim and Khosla apply the panel method of hydrodynamic analysis to develop analytic approximations to stream functions for complex geometry in [8]. Akishita et al. [9] have investigated the use of analytic harmonic functions based on ?uid dynamics in an approach similar to that found here. For a more exhaustive review of the literature on potential ?eld navigation, particularly with respect to the application of PDE solutions to path planning, the reader



is referred to the introduction to [10]. Further extensions and applications of the theory presented here can be found in [11], [12]. An alternative approach to collision avoidance that may have complementary applications to this work is the use of gyroscopic forces, introduced in [13] and discussed with particular application to multiple vehicle systems in [14]. This paper outlines a method for synthesizing stream functions which avoid obstacles while producing paths suitable for an aircraft-like vehicle. The contributions of this paper include the thorough exploration of methods for composing analytic stream functions and the explicit treatment of obstacle motion. In Section II an overview of potential and stream functions is given along with some mathematical preliminaries describing methods for constructing harmonic functions. An historic exact result from hydrodynamics for avoiding a single stationary obstacle is given in Section III and simulation results are presented; issues encountered when applying this technique to multiple obstacles are also described. Section IV describes a method by which obstacle motion can be incorporated into the stream function in an exact way. This approach, although similar to that of [9], includes a new proof of correctness and is the primary contribution of this paper. Section V contains a description of one implementation of this method and experimental results obtained on the Cornell RoboFlag/RoboCup testbed are discussed. A detailed examination of a new method proposed for modifying the existing theory to incorporate multiple obstacles exactly is presented in Section VI. Section VII describes a few additional applications of stream function-based navigation currently being explored and discusses possible ties between this work and the gyroscopic force methods presented in [13], [14]. Finally, Section VIII provides a summary and discusses the ongoing theoretical and experimental work related to this method. II. P RELIMINARIES A. Potential Fields Potential ?eld navigation is based on vehicles following the (sometimes negated) gradient of an arti?cial potential ?eld. Desirable properties for such a potential ?eld are: (1) Unique global minimum at goal state. (2) Gradient is exterior directed (or tangent) on boundaries of workspace. (3) Absence of local extrema corresponding to undesired equilibria in the resulting vector ?eld. Property (1) is not dif?cult; it is often satis?ed by having the ?eld shrink to ?∞ at the goal. Property (2) ensures obstacle avoidance, provided that the vehicle is capable of following the vector ?eld. Property (3) guarantees that vehicles will not come to rest at a location other than the goal state. Koditschek and Rimon showed by topological arguments in [6] that a vector ?eld in a workspace with m obstacles will contain at least m extra equilibria, and that through careful formulation one can guarantee that these equilibria will be saddle points. This means that a robot following the gradient will reach the goal state from any initial condition excepting a set of measure zero corresponding to the regions of attraction of the saddle points.

One method for ensuring that an arti?cial potential ?eld contains no local extrema is to formulate it as a harmonic function: De?nition 2.1 (Harmonic function [15]): A complexvalued function φ : Rn → C which is continuous and twice differentiable on an open, nonempty subset ? of Rn and which satis?es Laplace’s equation, ?2φ ?2φ ?2φ + + ... + = 0, (1) 2 2 ?x1 ?x2 ?x2 n is called a harmonic function on ?. The next theorems, adapted from [15], show that harmonic functions can have no local extrema. Let B (p, r) denote the open ball of radius r centered at p, and let B (p, r) be its closure. Theorem 2.1 (Mean-Value Property): If φ is harmonic on B (p, r) then φ(p) equals the average of φ over B (p, r). More precisely, 1 φ(p) = u dV. (2) V (B (p, r)) B (p,r) Theorem 2.2 (Maximum Principle): Suppose φ is realvalued and harmonic on a connected subset ? of Rn and has a maximum or minimum in ?. Then φ is constant. Proof: Suppose φ attains a maximum at p ∈ ?. Choose r > 0 such that B (p, r) ? ?. If φ(p ) < φ(p) for some p ∈ B (p, r), then the continuity of φ would imply that the average of φ over B (p, r) is less than φ(p), contradicting (2). Therefore φ is constant on B (p, r) and so the set where φ attains its maximum is open in ?. By the continuity of φ, this set must also be closed in ?. Hence this set must be all of ? and φ is constant on ?. The following corollary follows immediately from this theorem and is the most important property of harmonic functions in the context of this work. Corollary 2.1: Suppose ? is bounded and φ is a continuous, non-constant, real-valued function on ? that is harmonic on ?. Then φ has no local extrema in ?. ?2 φ B. Complex Functions The machinery of complex variables provides a convenient method for synthesizing harmonic functions in two dimensions which will be useful in the following sections. The following de?nitions and theorems are all adapted from [16]. Let z = x + iy be a complex variable with complex conjugate z = x ? iy . A function f : C → C of z which is ?nite and single-valued within a closed contour C ? C and which has a single-valued ?nite differential coef?cient with respect to z within C is said to be holomorphic. If the function f (z ) is taken to be φ(x, y )+ iψ (x, y ), the following conditions are necessary and suf?cient for f (z ) to be holomorphic: (1) ?f ?z = 0 within C . ?φ ?ψ ?ψ (2) All of the partial derivatives ?φ ?x , ?y , ?x , ?y are continuous. Theorem 2.3 (Cauchy-Riemann equations): Let f (z ) = φ(x, y ) + iψ (x, y ) = φ + iψ , where φ, ψ : R2 → R. Suppose ?f ?z = 0. Then ?φ ?ψ = , ?x ?y ?ψ ?φ =? . ?x ?y (3)



These are known as the Cauchy-Riemann equations. 1 Proof: Note that x = 1 2 (z + z ) and y = ? 2 i(z ? z ) for z ∈ C. Then ?f ?f ?x ?f ?y =0 = + ?z ?x ?z ?y ?z 1 ?f 1 ?f = + i 2 ?x 2 ?y 1 ?φ ?ψ ?ψ 1 ?φ = +i +i + i . 2 ?x ?x 2 ?y ?y Setting the real and imaginary components of this equation equal to zero gives the desired result. The real and imaginary parts of a holomorphic function of z are called conjugate functions. For example, φ and ψ in Theorem 2.3 above are conjugate functions. Theorem 2.4 (Solutions to Laplace’s Equation): Conjugate functions are solutions to Laplace’s equation. Proof: The Cauchy-Riemann equations give: ?φ ?ψ ?ψ ?φ = , =? . ?x ?y ?x ?y Differentiating and substituting yields: ?2ψ ?2ψ ?2φ ?2φ + = 0 , + = 0. ?x2 ?y 2 ?x2 ?y 2 and Laplace’s equation is satis?ed by both φ and ψ . The preceding theorems show that we can construct local extrema-free potential functions in R2 simply by taking the real or imaginary components of arbitrary holomorphic functions in C. In the sequel we will explore how to encode the desired navigation properties in the underlying complex function. C. Stream Functions The following de?nitions and theorems are again taken from [16]. Incompressible, inviscid, irrotational ?uid ?ow can be described in terms of potential functions in which the ?ow is always along the gradient of the ?uid potential. A stream function is a more general function which describes incompressible ?ow which may be viscous and/or rotational in which the ?ow is along the level curves of the function, i.e. the level curves are the streamlines of the ?ow: De?nition 2.2 (Stream Function): A stream function ψ gives the components u, v of ?uid velocity in the xy plane by ?ψ ?ψ u=? , v= . (4) ?y ?x 2 ? ψ describes the vorticity of the ?ow. If the ?ow is irrotational in a region W , ?2 ψ = 0, ψ is a harmonic function on W , and the potential function φ exists [16]. De?nition 2.3 (Complex Potential): The complex potential w of an irrotational two-dimensional ?ow of an inviscid liquid is de?ned by w = φ + iψ, (5) where φ and ψ are the potential and stream functions de?ning the ?ow. Equating the velocity components gives ?ψ ?φ = , ?x ?y ?φ ?ψ =? , ?y ?x

which are exactly the Cauchy-Riemann equations. Thus we see that w is a holomorphic function of z = x + iy in any region where φ and ψ are single-valued. Conversely, we can assume for w any holomorphic function of z and the real and imaginary parts give the potential and stream functions for a possible ?ow satisfying Laplace’s equation. The insertion of an obstacle into a ?ow introduces the boundary condition that the ?ow be tangent to the surface. Because ψ is constant along a streamline, this is equivalent to the condition that the stream function must be constant on an obstacle’s surface. The problem of enforcing the tangent boundary condition then becomes one of ensuring that the complex potential has constant imaginary part on the obstacle boundary. The following theorem is taken from [16] and adapted for arbitrary obstacle locations. Theorem 2.5 (Circle Theorem): Let there be irrotational two-dimensional ?ow of incompressible inviscid ?uid in the z -plane. Let there be no rigid boundaries and let the complex potential of the ?ow be f (z ), where the singularities of f (z ) are all at a distance greater than a from the point b. If a circular cylinder, typi?ed by its cross-section the circle C, |z ? b| = a, is introduced into the ?ow, the complex potential becomes a2 +b . (6) z?b Proof: On the circle, |z ? b| = a. Thus w reduces to w = φ + iψ = f (z ) + f w = f (z ) + f (z ) which is purely real and therefore ψ = 0 and C is a streamline. The new complex potential w is the sum of holomorphic functions and thus is itself holomorphic, so the conjugate functions φ and ψ satisfy Laplace’s equation. If a point z is 2 outside C , the point za ?b + b is inside C , and vice-versa. Since all the singularities of f (z ) are by hypothesis exterior to C , 2 all the singularities of f ( za ?b + b) are interior to C . Thus w has exactly the same singularities as f (z ) and all conditions are satis?ed. III. AVOIDANCE OF A S TATIONARY O BSTACLE The Circle Theorem allows the stream function for a vehicle to be composed of primitives which describe different vehicle behaviors. The most useful primitives for robot navigation are the sink, fs (z ), and the vortex, fv (z ): fs ( z ) = fv (z ) = ?C ln(z ), C i ln(z ), (7) (8)

where C ∈ R+ is the strength of the singularity associated with the primitive, which is assumed without loss of generality to be located at the origin. In the case of a sink ?ow of strength C into which a single, stationary obstacle of radius a is placed at (x, y ) = (bx , by ) and letting b = bx +iby , applying the Circle Theorem gives the complex potential w = ?C ln(z ) ? C ln a2 +b . z?b



The imaginary component of this complex potential is the stream function for the ?ow y ψ = ?C tan?1 (9) x ? ? a2 (y ?by ) 2 2 + by ?1 ? (x?bx ) +(y ?by ) ?. + C tan a2 (x?bx ) + b x (x?bx )2 +(y ?by )2 Note that on the surface of the obstacle (x ? bx )2 + (y ? by )2 = a2 and thus ψ = 0, verifying that the ?ow is tangent to the surface. Differentiating using the de?nition of the stream function above yields the components u and v of the ?ow velocity, u = v where Wu Wv M = = = bx (x ? bx )2 + a2 (x ? bx ) + (y ? by )(2by x ? bx (y + by )), by (y ? by )2 + a2 (y ? by ) + (x ? bx )(2bx y ? by (x + bx )), 2 2 a4 + 2a2 (bx (x ? bx ) + by (y ? by )) + (b2 x + by )ro . = ?C ?C x +C x2 + y 2 y +C 2 x + y2 a ro a ro

Fig. 4.

Multiple obstacle avoidance.

Wu , M Wv , M



separately by the above methods has been quite successful in both simulation and experiment as long as the obstacles are not nearly touching one another. Fig. 4 depicts simulation results for a vehicle negotiating a group of obstacles. Work is in progress to determine more precisely how accurate this approximation is, and a method by which these results can be applied exactly to the case of multiple obstacles is proposed in Section VI.

IV. M OVING O BSTACLES If the obstacles to be avoided are moving, simply using a snapshot of the con?guration space at each instant in time to calculate a quasi-static potential ?eld will be insuf?cient to guarantee obstacle avoidance. This can be seen by imagining that the vehicle is in?nitesimally close to the leading edge of a moving obstacle at a particular instant. A navigation function is guaranteed to be exterior directed (or at least tangent, in the case of stream functions) on the boundary, but does not guarantee that it will produce a vehicle motion which will be fast enough (ignoring actuator constraints) to stay ahead of the obstacle. Furthermore, a quasi-static potential function may also generate undesirable behavior even if obstacle avoidance is successful in that it may direct a vehicle to pass in front of an obstacle rather than behind it. Both of these issues can be dealt with by a change of reference frame in which the condition for obstacle avoidance becomes that the vector ?eld must be exterior (or tangent) directed on the boundary of the obstacle in the rest frame of the obstacle. Stream functions offer a convenient method for handling this condition. Theorem 4.1 (Stream Function for a Moving Obstacle): Consider a circular obstacle in an arbitrary irrotational two-dimensional ?ow of incompressible inviscid ?uid with complex potential f (z ) as in the Circle Theorem above. Let the obstacle be moving at constant velocity v0 = vx + ivy . The complex potential for the ?ow about the obstacle is given by w(z ) = ws (z ) ? vx a2 + b ? ivy z?b a2 + b , (11) z?b

In practice, the constant C is arbitrary and the velocity is normalized to respect vehicle dynamics while preserving its direction. The object created upon application of the Circle Theorem is called a doublet and is essentially the limit as a singular source (de?ned as a sink, above, but with ?C replaced by C ) and sink are brought together. Fig. 2(a) depicts the streamlines (level curves of the stream function) of a doublet alone. The important effect of this composition is that, in contrast to the objects created by most other potential ?eld methods, the doublet carries with it the notion of an orientation. The effect of the doublet depends not only on the vehicle’s position relative to it, but also upon where the vehicle is going. This helps to produce the smooth paths observed when using this method, and also tends to produce commands in the direction which one would intuitively guess to be “correct” to gently veer around an obstacle. Fig. 2(b) depicts the streamlines obtained from the Circle Theorem for a sink ?ow with an obstacle. Note that the paths generated by following the streamlines tend to be smooth due to the tangent boundary condition; i.e. they appear at least qualitatively to be well-suited to the dynamics of an aircraftlike vehicle. Fig. 3 compares simulations of the paths a fully¨ = u dynamics would follow given a actuated vehicle with x potential function following the formulation of [6] and one generated by the method presented here for the same initial conditions, obstacle location, and goal position. All of the above statements apply exactly only to the case of a single obstacle. However, in a simple ?ow such as a sink (or source) or vortex ?ow, the in?uence of an obstacle falls off with the square of the distance to the obstacle. When multiple obstacles are present, treating each obstacle

where ws is the static stream function that would be derived if the obstacle were not moving. Proof: Performing a Galilean transformation into the reference frame of the obstacle superimposes ?v0 on the velocity ?eld given by w(z ). The complex potential for this uniform ?ow is g (z ) = ?vx z + ivy z , so the complex potential



(a) Doublet streamlines Fig. 2. Obstacle avoidance streamlines.

(b) Obstacle avoidance

(a) Potential ?eld Fig. 3. Comparison of obstacle avoidance approaches.

(b) Stream function

described by (11) in this reference frame is given by w (z ) = ws (z ) ? vx z + ivy z a2 a2 ? vx + b ? ivy +b z?b z?b a2 = f (z ) + f +b z?b a2 + g (z ) + g +b , z?b

Fig. 6.

RoboFlag testbed.

which is the result given by applying the Circle Theorem to the ?ow in the rest frame of the obstacle. Thus the vector ?eld is tangent to the obstacle boundary in the reference frame of the obstacle and a vehicle following the vector ?eld will not hit the obstacle. The result of the above theorem is to add an additional doublet which describes how the vehicle should pass around the moving obstacle. Note that in contrast to the sink strength discussed above, the strength of this doublet is not arbitrary; it is that required to avoid the moving obstacle and it is set by the magnitude of the obstacle’s velocity. Fig. 5 depicts simulation results for goal seeking with and without the additional dynamic component of the stream function in place. The vehicle is depicted as a series of outlined circles representing equal time steps, and the obstacle is depicted as solid circles at the same set of times. The obstacle is moving on a circular trajectory at a constant speed equal to the maximum speed of the vehicle. In Fig. 5(a) the vehicle attempts unsuccessfully to pass in front of the obstacle and

a collision takes place. In Fig. 5(b), the vehicle successfully avoids the obstacle by passing behind it. V. E XPERIMENTAL R ESULTS Stream function-based navigation has been implemented on Cornell University’s RoboFlag/RoboCup testbed [1], shown in Fig. 6. The RoboFlag vehicles are omni-directional and capable of following nearly arbitrary trajectories, and so are an ideal testbed for the initial implementation of these concepts. Furthermore, the input to the low-level controllers on the vehicles is the desired velocity, so stream functions are particularly suited to generating the control inputs. The current experimental implementation requires the velocity obtained from the stream function to be normalized to suit the dynamics of the vehicle as well as the desired speed range. In the case of static obstacle avoidance, the simple dynamics of the RoboFlag vehicles allows them to



(a) No dynamic component

(b) With dynamic component

Fig. 5. Moving obstacle avoidance. Vehicle (open circle) attempts to travel to destination marked ‘x’ while avoiding moving obstacle (shaded circle). Obstacle follows a set circular trajectory.

travel at nearly their maximum speed all of the time, so the normalization simply retained the direction of the stream function-commanded velocity and set the velocity to this maximum. When the obstacles were moving, however, a different approach was necessary. The equations from Section IV separate into two independent components: one due to the external ?ow and static obstacle con?guration, and one due to the motion of the obstacle. As discussed above, the magnitude of the velocity due to the static con?guration and goal is arbitrary prior to normalization, but the magnitude of the velocity due to the obstacle motion has physical meaning. Hence, when normalizing commands to satisfy actuator constraints, the dynamic component was entirely satis?ed and any remaining actuator authority was devoted to the static component. Obstacle avoidance was guaranteed because the external ?ow was given the maximum strength possible that would allow the vehicle to preserve the intended direction of travel. That is, the normalization was given by maximizing the sink strength C with the constraints C vs + vd ≤ vmax , |vs | ˙ | ≤ amax , |v (12)

Fig. 7. Multiple obstacle avoidance – RoboFlag experimental results. Vehicle (open circles) travels from home zone in top left of ?gure to capture ?ag (black dot) in opponents ?ag zone while avoiding stationary obstacles (?lled circles). Time span is approximately 10s, with 0.3s between frames.

where vs and vd are the static and dynamic velocity components and vmax and amax are the maximum speed and acceleration constraints on vehicle motion. Several maneuvers were performed at a maximum speed of 0.6 m/s. The ?rst maneuver was a “capture the ?ag” exercise. Using sink stream functions, the vehicle was commanded to start out at a home location, travel about 4 meters to a point and stop there, then return to the initial location, all while avoiding stationary obstacles placed randomly on the ?eld. The vehicle was consistently able to perform this maneuver without coming into contact with the obstacles as long as the obstacle con?guration was relatively sparse, e.g. about four obstacles in the path from home to goal. Fig. 7 depicts one such test run spanning 10 seconds. During this run the proposed correction to make multiple obstacle avoidance exact described in Section VI was in place. The second maneuver tested was an orbit/defend maneuver.

The vehicle was commanded to circle a particular point at a 1-meter radius. Control of the radius was implemented via source/sink ?ows at the orbit center, and the orbit itself was implemented using a vortex. Obstacle avoidance was again demonstrated in this maneuver. Multiple vehicles were able to perform this maneuver together, spacing themselves equally about the circle by monitoring the positions of the other vehicles and adjusting their own maximum speed to compensate. The third maneuver tested was avoidance of moving obstacles. Three vehicles were commanded to circle the destination of a ?ag-capturing robot without avoiding obstacles. The “capture the ?ag” maneuver was then run both with and without the dynamic component of the stream function present. Performance without the dynamic component was very poor — unless the vehicle happened to be approaching the goal at exactly the right time, it would collide with one of the passively moving “defenders,” often because the static stream function commanded it to try to pass in front of the moving obstacle. The introduction of the dynamic stream function (normalized using (12)) improved performance dramatically.



With this component in place, the attacker could generally capture the ?ag and return without collision, following a path that would take it behind a defender when necessary rather than trying to hook around in front. In all demonstrations the effects of having multiple rather than a single obstacle seemed to be negligible as long as the obstacles were at least one obstacle diameter apart. Demonstrations of all maneuvers in simulation were much more successful at dealing with higher obstacle densities; high latency in the system (on the order of 500 ms) was the likely cause for this discrepancy. Movies of the experiments described above are available online at http://www.cds.caltech.edu/ ?waydo/streammovies/streammovies.html

by contradiction. a2 + ro a
2 2 b2 x + 2xbx ? 2bx

≤ ≤ ≤ ≤

x2 + y 2
2 x2 ? 2xbx + b2 x+y 2 ro

ro 2 2 bx ? b2 x a 2 r o 2 a2 + b2 x ? bx a 2 ro 2 bx ?1 a a a2 +

bx a




ro 2 ≤ 1, a which violates the condition that a/ro < 1. This fact allows us to interpolate between the single obstacle cases without generating new equilibria. Let the con?guration space contain m obstacles, with the ith obstacle, i = 1, . . . , m, having radius ai and location (bxi , byi ). Let ui and vi denote the x and y velocity components that would exist for a sink ?ow about obstacle i on its own. De?ne m distance functions di : R2 → R, di =
2 2 (x2 ? b2 xi ) + y ? byi 2 2

The current focus of this work is to improve the treatment of multiple obstacles. Attempts to solve Laplace’s equation analytically with the multiple obstacle boundary condition have not been fruitful, but another approach which involves interpolating between the single-obstacle cases may be of use in the most important case, that of a goal-seeking (sink) ?ow. First it is necessary to re-examine the velocity ?eld in a sink ?ow with obstacle in a bit more detail. The x and y components u and v of the ?ow velocity are given by (10). Assume without loss of generality that C = 1. Let ro be the distance from the point (x, y ) to the center of 2 an obstacle located at (bx , by ), i.e. ro = (x ? bx )2 + (y ? by )2 and let a be the obstacle radius. Lemma 6.1: The velocity ?eld resulting from a circular obstacle being placed in a sink ?ow always has a non-zero component directed toward the origin outside the obstacle (i.e. when ro > a). Proof: The component of the velocity ?eld due to the sink is always directed toward the origin and has magnitude 1 (x2 + y 2 )? 2 . Hence, it is suf?cient to show that the magnitude of the velocity due to the doublet is always smaller than this when ro > a. Because of symmetry we can set by = 0 and bx > 0 without loss of generality (Note that because the obstacle may not overlap the goal point, bx > a). With this substitution and after some algebra the magnitude of the velocity due to the doublet becomes a ro

? ai ,

which is the distance from the point (x, y ) to the boundary of the ith obstacle. Finally, de?ne interpolation functions on the di ’s as αi : Rm → [0, 1] with the following constraints: αi αi αi = 0 when dj = 0 ? j = i = 1 when di = 0 ∈ (0, 1) when dk > 0 ? k, dj . di + dj (13)

where i, j, k ∈ [1, 2, . . . , m]. One such function is αi =
j =i

The proposed form of the ?nal velocity ?eld is u=

αi ui ,


αi vi .


This interpolation guarantees that on an obstacle surface the vector ?eld will be exactly that which would have existed in the presence of that obstacle alone; thus it guarantees obstacle avoidance as above. Because it is no longer the gradient of a harmonic function, the velocity ?eld is no longer guaranteed by the previous proofs to have no spurious equilibria and a new proof is required. Theorem 6.1: Composing stream-function-based velocity ?elds using Eqns. (13) and (14) will create no new equilibria. Proof: Decompose the velocity ?eld induced by each obstacle into radial and tangential components, (ui , vi ) → (vri , vθi ). The total velocity ?eld is then vr = αi vri ,

|vd | =

1 a2 + b2 x
ro 2 a

vθ =

αi vθi .

. + 2xbx ? 2b2 x

Since a/ro < 1 outside the obstacle it is now suf?cient to 2 2 2 2 show that a2 + b2 x (ro /a) + 2xbx ? 2bx > x + y . We do so

By the lemma, vri < 0 for all i away from the surface of any obstacle, and so because αi > 0 for all i the total radial 2 + v 2 = 0 away velocity vr < 0. Thus the total velocity vr θ from the obstacles and the ?eld has no local equilibria. On the surface of an obstacle, the velocity ?eld is exactly that given



Fig. 8. Simulation of a UAV carrying out a mission using stream function path planning. Vehicle navigates from position marked “start” to position marked “goal.” while attempting to avoid threat zones (dashed circles). Threat zones are treated as “soft” obstacles to open a path for the vehicle.

by the obstacle in the sink ?ow alone, and so any equilibrium on the surface must be a saddle point as before. VII. OTHER A PPLICATIONS AND O NGOING W ORK In [12], methods for using stream functions to generate more complex trajectories and behaviors than those presented here are discussed. This work also examines several new methods for accommodating workspaces with multiple obstacles, with the goal of safely navigating an unmanned aircraft through hostile territory. For this application the “obstacles” are generally spheres of in?uence of enemy antiaircraft installations. One interesting aspect of this work is that there may not exist a path to the destination that fully avoids all of these obstacles, and dynamic resizing of the perceived obstacles (which are then known as “soft obstacles”) is used to open paths while attempting to minimize exposure to danger. Fig. 8 depicts a simulation of a UAV navigating through hostile territory using a stream function planner and incorporating these techniques. The dashed circles represent zones of in?uence of enemy threats. Note that in this case there is no totally clear path between the starting an ?nal conditions, but the use of the soft obstacle techniques mentioned above enables the UAV to reach its destination while minimizing the time spent in dangerous regions. A single waypoint is also used in this simulation to guide the vehicle’s progress; the kink visible in the path is the point at which the destination is suddenly switched. This work also examines the use of simulated spring forces between vehicles as a means of maintaining formation while using a stream function as a path planner. Two approaches are discussed: that of a leader aircraft following a stream function while the follower aircraft maintain formation, and one in which each aircraft independently follows a stream function to its desired goal while also feeling the effect of spring forces that maintain group cohesion.

Another obstacle avoidance methodology that may have important connections to this work is the use of gyroscopic forces. Gyroscopic forces can be thought of as steering forces, as they always act perpendicular to the velocity vector. Obstacle avoidance is not implemented using a vector ?eld in this case, so the topological dif?culties described by Koditshek and Rimon in [6] can be circumvented. The use of such forces for obstacle avoidance is introduced in [13] and examined in the context of multiple vehicle systems in [14]. In both of these papers a potential function is used to induce goal-seeking behavior while the gyroscopic forces are used for obstacle avoidance. Because of this formulation, it may be possible to use stream functions and gyroscopic forces simultaneously in a complementary way. A stream function could be used as a high-level path planner used to generate a smooth path from start to goal that avoids dangerous regions, as in [12], and then gyroscopic forces superimposed to handle lowerlevel obstacle avoidance. It appears that it will be easier to explicitly address non-trivial vehicle dynamics within the gyroscopic force framework, and so passing the low-level obstacle avoidance down to a gyroscopic force algorithm may be a convenient method to address this issue. Such a hierarchical framework may also have applications in control of multiple vehicle systems, in which a stream function could be used to generate the potential that each vehicle in the group follows while inter-vehicle collisions are prevented by gyroscopic forces. VIII. C ONCLUSION This paper has presented a method for composing localextrema free potential ?elds for vehicle guidance using stream functions. These functions provide avoidance of moving obstacles while allowing ?exibility in designing the overarching vehicle behavior. While the results presented above apply exactly only to the case of a single obstacle, a promising method for treating multiple obstacles exactly has been found. Future work will focus on several key areas outlined below. An important extension needed to fully exploit the possible applications of stream functions will be that to a threedimensional workspace. The complex potential approach is inherently two-dimensional and will not extend readily to this case. Two possibilities arise here. It may be that suitable three-dimensional problems can be posed as multiple lower-dimensional problems to be solved simultaneously. For example, altitude control of an aircraft may be performed as a separate function from navigation in the plane and the planar navigation problem solved via the above methods. Also, because complex functions are only used as part of the synthesis and analysis problems and do not show up in the ?nal stream function, there may be extensions of the above results to three dimensions obtainable without the complex variables machinery. While the paths generated by the stream function method appear more likely to be suited to vehicles such as aircraft than those produced by other means, there is no explicit consideration of vehicle dynamics in the above formulations. The guarantees of obstacle avoidance rest on the assumption



that the vehicle follows exactly the streamlines of the ?ow. Other methods, for example that followed by Koditschek and Rimon in [6], do provide guaranteed obstacle avoidance for actuator-limited vehicles by bounding the system energy (including that of the arti?cial potential). Such proofs, however, rely on the vehicle’s ability to produce force in any direction and the resulting trajectories may not be feasible for aircraftlike vehicles. Another area for future research is to develop a quantitative understanding of the motion described by stream functions and how vehicle dynamics including under-actuation and minimum speed requirements might be incorporated into synthesis. In addition to the above questions regarding the current theory, future work will focus on handling multiple vehicle formations in the stream function framework. It may be that “?exible” formation ?ight and obstacle avoidance can be incorporated together by having vehicles act as if they are part of a viscous “blob” suspended in an inviscid ?uid; this may be an adaptation of the virtual leader method as in [17]. It is hoped that this type of approach will naturally lead to formations that adapt themselves to the environment; for example, a circular formation may become longer and narrower as it passes between obstacles. The approach explored in [12] in which each vehicle follows a stream function while also feeling a spring force maintaining formation appears to be a start along these lines. The use of gyroscopic forces as discussed above may prove to be complementary to this method and could help to resolve some of the issues raised here, speci?cally explicit consideration of vehicle dynamics and control of groups of vehicles. Another important area of future work is to examine in detail possible ways to integrate the work described here with the gyroscopic force formulation. Several experimental thrusts are planned for the near future as well. The current obstacle avoidance libraries available for use on the RoboFlag testbed include stream functions as an option, so any future experiments on the testbed can also be used to further explore stream functions. Longer term testing plans include implementing stream function-based control on the Caltech Multi-Vehicle Wireless Testbed (MVWT) [18], [19]. The vehicles associated with this testbed rest on omnidirectional casters and are powered by two ?xed ducted fans; thus, they have the aircraft-like dynamics that this theory was developed to address. ACKNOWLEDGMENTS Work described in this paper was supported in part by the Defense Advance Research Projects Agency under cooperative agreement F30602-01-2-0577 with the Air Force Research Laboratory, Information Directorate, with Lt Col Sharon Heise, PhD as the Program Manager, and Mr. Carl DeFranco from AFRL Rome Laboratory as Technical Agent. Additional support was provided by the Fannie and John Hertz Foundation. R EFERENCES
[1] R. D’Andrea and M. Babish, “The RoboFlag test-bed,” in Proc. of the American Control Conference, 2003.

[2] R. D’Andrea and R. M. Murray, “The RoboFlag competitions,” in Proc. of the American Control Conference, 2003. [3] R. M. Murray, Ed., Control in an Information Rich World. SIAM, 2003, pp. 54–55, (to appear). Available online: http://www.cds.caltech. edu/?murray/cdspanel. [4] S. A. Heise. Mixed initiative control of automateams. [Online]. Available: http://dtsn.darpa.mil/ixo/mica.asp [5] O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” International Journal of Robotics Research, vol. 5, no. 1, pp. 90–98, 1986. [6] D. E. Koditschek and E. Rimon, “Robot navigation functions on manifolds with boundary,” Advances in Applied Mathematics, vol. 11, pp. 412–442, 1990. [7] C. I. Connolly and R. A. Grupen, “On the applications of harmonic functions to robotics.” [8] J.-O. Kim and P. K. Khosla, “Real-time obstacle avoidance using harmonic potential functions,” IEEE Trans. on Robotics and Automation, vol. 8, no. 3, pp. 338–349, 1992. [9] S. Akishita, S. Kawamura, and T. Hisanobu, “Velocity potential approach to path planning for avoiding moving obstacles,” Advanced Robotics, vol. 7, no. 5, pp. 463–478, 1993. [10] S. A. Masoud and A. A. Masoud, “Constrained motion control using vector potential ?elds,” IEEE Trans. on Systems, Man, and Cybernetics, vol. 30, no. 3, pp. 251–272, May 2000. [11] M. Campbell, R. D’Andrea, D. Schneider, A. Chaudhry, S. Waydo, J. Sullivan, J. Veverka, and A. Klochko, “RoboFlag games using systems based, hierarchical control,” in Proc. of the American Control Conference, 2003. [12] J. Sullivan, S. Waydo, and M. Campbell, “Using stream functions for complex behavior and path generation,” in To appear: AIAA Guidance, Navigation, and Control Conference, 2003. [13] D. Chang and J. E. Marsden, “Gyroscopic forces and collision avoidance with convex obstacles,” in To appear: Proc. of the 60th Birthday Conference in honor of Art Krener, 2003. [14] D. Chang, S. Shadden, J. E. Marsden, and R. Olfati-Saber, “Collision avoidance for multiple agent systems,” in Submitted: Proc. of the Conference on Decision and Control, 2003. [15] S. Axler, P. Bourdon, and W. Ramey, Harmonic Function Theory, 2nd ed. Springer, 2001, pp. 1–9. [16] L. Milne-Thomson, Theoretical Hydrodynamics, 5th ed. Dover Publications, Inc., 1996. ¨ [17] P. Ogren, E. Fiorelli, and N. E. Leonard, “Formations with a mission: Stable coordination of vehicle group maneuvers,” in Proc. Symposium on Mathematical Theory of Networks and Systems, 2002. [18] T. Chung, L. Cremean, W. B. Dunbar, Z. Jin, E. Klavins, D. Moore, A. Tiwari, D. van Gogh, and S. Waydo, “A platform for cooperative and coordinated control of multiple vehicles: The Caltech Multi-Vehicle Wireless Testbed,” in To appear: Proc. of the 3rd Conference on Cooperative Control and Optimization, 2002. [Online]. Available: http://www.cds.caltech.edu/?mvwt/cco02-mvwt.pdf [19] L. Cremean, W. Dunbar, D. van Gogh, J. Hickey, E. Klavins, J. Meltzer, and R. M. Murray, “The Caltech Multi-Vehicle Wireless Testbed,” in Proc. of the Conference on Decision and Control, 2002.

John Doe Biography text here.




All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。