Real-time Reciprocal Collision Avoidance With Elliptical Agents
Real-time Reciprocal Collision Avoidance with Elliptical AgentsAndrew Best1 , Sahil Narang1 and Dinesh Manocha1http://gamma.cs.unc.edu/EORCA/Abstract— We present a novel algorithm for real-timecollision-free navigation between elliptical agents. Each robotor agent is represented using a tight-fitting 2D ellipse in theplane. We extend the reciprocal velocity obstacle formulationby using conservative linear approximations of ellipses andderive sufficient conditions for collision-free motion based onlow-dimensional linear programming. We use precomputedMinkowski Sum approximations for real-time and conservativecollision avoidance in large multi-agent environments. Finally,we present efficient techniques to update the orientation tocompute collision-free trajectories. Our algorithm can handlethousands of elliptical agents in real-time on a single core andprovides significant speedups over prior algorithms for ellipticalagents. We compare the runtime performance and behaviorwith circular agents on different benchmarks.I. INTRODUCTIONOne of the main issues in multi-robot planning and multiagent navigation is computing collision-free paths for eachrobot or agent from its start position to its goal position.This problem arises not only in robotics and AI, but also incomputer games, virtual environments, pedestrian dynamics,and simulations of collective behaviors in biology.In this paper, we mainly address the problem of real-timemulti-agent collision avoidance for large environments withhundreds or thousands of agents. Most practical algorithmsare based on decentralized methods that tend to compute apath for each robot or agent independently. Moreover, mostof these decentralized algorithms represent each agent as acircle in a 2D plane. This simplified disc representation hasa number of advantages. Discs are radially symmetric andthere are simple solutions to operations, including computingthe closest point on a disc to an arbitrary query point orchecking two discs for overlap. Many collision-avoidancealgorithms based on velocity obstacles [1], [2], [3] computeMinkowski Sums, which is rather trivial for discs. Thesymmetric properties are also used to design simple rulesfor flocking [4] or collision-avoidance schemes based onpotential fields or repulsive social forces [5].Despite the computational benefits, the use of discs formulti-agent navigation results in many challenges. In manycases, a disc overestimates the actual profile of the robotsthat it represents. The geometries of many robots, includinghumanoids and vehicles, are not radially symmetric. As aresult, disc-based collision-avoidance schemes can be overlyconservative. In other applications, tighter-fitting geometric*This work is supported by ARO contract W911NF-14-1-0437, and agrant from the Boeing company.1 Andrew Best, Sahil Narang and Dr. Dinesh Manocha are with thedepartment of Computer Science at the University of North Carolina atChapel Hill, 201 S. Columbia St, Chapel Hill, NC 27599-3175.shapes (e.g. ellipses) are considered more accurate. Forexample, elliptical shapes are used in motion planning algorithms for robots with linear dynamics [6] or to representuncertainty [7], [8]. Prior work in pedestrian dynamics andbiomechanics has shown that 2D ellipses provide a betterapproximation of human body in terms of shape and movement [9], [10].It is widely accepted that the use of ellipses for multiagent navigation can result in complex and time-consumingalgorithms. The underlying techniques must explicitly modelthe orientation of each ellipse. Moreover, computing exactMinkowski Sums of ellipses is regarded as considerablymore expensive than doing the same for circles [11]. Itis difficult to predict the behavior of force-based methods,as the formulation and computation of repulsive forces onelliptical agents is more complicated.Main Results: We present a novel real-time algorithmfor collision-free navigation of elliptical agents in dynamicenvironments. We use a decentralized approach based onvelocity obstacles [2], [3] and present fast algorithms forconservative collision avoidance. To overcome the complexity of exact Minkowski Sum computation, we use conservative linear approximations of ellipses and reduce thecollision avoidance problem to solve a lower dimensionallinear programming problem and show that our formulationis reciprocally maximal. To ensure that we can handlelarge environments consisting of hundreds or thousands ofagents in real-time, we use precomputed tables of MinkowskiSums and guarantee that feasible trajectories computed usingour algorithm would be collision-free. We also present atechnique to update the orientation of ellipses in denseenvironments to compute collision-free trajectories amongstatic obstacles or to generate human-like trajectories. Inpractice, the use of conservative linear approximations andprecomputed Minkowski Sums tables improves the runtimeperformance by more than an order of magnitude. Ouroverall algorithm can perform collision-free navigation ofthousands of agents at interactive rates on a single core andis only 4 5X slower than collision avoidance algorithmsfor circular agents. We highlight its performance in complexenvironments and demonstrate the benefits.The rest of the paper is organized as follows. In SectionII, we provide a brief overview of prior work in multiagent navigation and collision avoidance algorithms. Weintroduce the notation and present our optimal collisionavoidance algorithm between elliptical agents in Section III.In Section IV, we present our acceleration scheme basedon precomputed Minkowski Sum tables. We describe two
different methods to update the orientation of elliptical agentsin Section V. We highlight our algorithm’s performance indifferent environments in Section VI.II. RELATED WORKThere is a substantial body of work on motion planningand navigation for single or multi-robot systems. Someearlier methods were designed for static environments.At a broad level, prior algorithms for collision-free navigation can be classified as centralized and decentralized.Centralized planners treat the set of all robots as a singlesystem in a (very) high-dimensional configuration space, andmany well-known methods for single-robot motion planningcan be used [12], [13], [14]. These planners have the advantage of being complete (in theory), but practical algorithmsare limited to systems with a few robots. Decentralizedplanners tend to compute a path for each robot or agentindependently, and use some coordination mechanism orlocal navigation techniques to avoid collisions between them.Many techniques have also been proposed for collisionavoidance, navigation, and planning among moving obstacles[15], [16], [17], [18], and these can be extended to ellipticalagents. Given an agent, all the other agents can be treatedas dynamic obstacles along with other objects in the scene.However, these methods do not consider the reactive behavior of other agents as part of multi-agent planning.Many decentralized planners tend to rely on high-levelplanning modules to generate paths through the static environment and on local collision-avoidance algorithms to adaptthose plans to the environment. Priority-based methods assign order to the robots, and plan the paths sequentially [19].Velocity-obstacle based methods compute locally collisionfree velocities in velocity space [1], [20], [2], [3]. Whereasmany local collision-avoidance algorithms take advantage ofthe disc representation of the robots, some algorithms alsoattempt to model additional dynamics constraints, such asdifferential-drive [21], double-integrator [22], car-like [23],or linear [24], etc., or they use reciprocally rotating velocity obstacles [25]. The two dimensional disc collisionavoidance problem has also been extensively studied in thecrowd simulation and pedestrian dynamics literature. Thesestudies include force-based methods [5], [26], [27], cellulardecomposition methods [28], rule-based methods [4], etc.Although all these algorithms are fast, they are limited tocircular agents.III. MULTI-AGENT COLLISION AVOIDANCEWITH ELLIPTICAL AGENTSIn this paper, we address the problem of the efficientnavigation of multiple elliptical agents. We first introducethe notation used in the rest of the paper. Let Rd representthe physical workspace of the robots or agents, where d 2.For simplicity, we assume each agent can be represented inR2 . We project the geometric representation Od of the robotin Rd space to R2 , represented by O2 , and bound it with anellipse in R2 .A. PROBLEM DEFINITIONLet S represent the simulator state, defined as the unionof all entities in the scene, including obstacles in the environment and the overall state space X i Xi , where Xidenotes the state space of robot i [29]. The elliptical shapein R2 for each robot i is defined by the position vectorp i R2 , orientation oi R, the semi-major axis smaj R ,imin and the semi-minor axis si R where orientation isdefined as the angle between the major axis and the x-axisof the reference frame. Also, let vi0 represent the optimalvelocity toward the goal with respect to static obstacles (alsocalled the preferred velocity) and let o0 denote the preferredorientation for the robot. Then the state space of robot i inR10 is given by [ pi , vi , vi0 , oi , o0i , smaj, smin].iiWe assume that there is a high-level module Ki : t S R2 that maps the time t and simulator state S into aninstantaneous preferred velocity that can be expressed as thecomposition of simpler functions such asKi (t) Pi (Gi (t)),(1)where Gi : t S R2 maps the time and simulatorstate into a goal position and Pi : S R2 R2 thatmaps the simulator state and the agent’s goal position intoa instantaneous preferred velocity for agent i, denoted by vio . The function Ki computes the collision-free path tothe goal with respect to static obstacles in the simulation.Let LCAi : S R2 R2 R R2 R2 denote alocal collision avoidance function that maps the simulatorstate, the instantaneous preferred velocity, the instantaneouspreferred orientation, and time horizon, τ , into a collisionfree orientation (oi ) and velocity ( vi ) with respect to otherrobots in the environment for at least time τ .Our goal is to formulate a generalized local collisionavoidance function LCA for elliptical agents, which seeksto independently and simultaneously compute a velocity viand orientation oi for each elliptical robot i in the simulation.Thus, the instantaneous velocity and orientation of an agentcan be given by:( vi (t), oi (t)) LCAi (Hi (Pi (Gi (t)))),2(2)2where Hi : S R R R maps the simulator state,preferred velocity, and time to the preferred orientation. Thefunction LCA must guarantee that all elliptical agents canfollow a collision-free trajectory with the new configurationfor at least a predefined horizon window of time τ . Furthermore, the agent’s new velocity should be as close as possibleto its preferred velocity.B. LOCAL COLLISION AVOIDANCEIn this section, we present our local collision-avoidancealgorithm for elliptical agents. Our algorithm is based on velocity obstacles that have been frequently used for collisionavoidance in robotics and crowd simulation [3], [2]. However, as with most prior work in multi-agent navigation, thesemethods are limited to agents represented as 2D discs.Velocity Obstacles: For two agents, X and Y , centered atp X and p Y , respectively, the velocity obstacle of X induced
τby Y , which is denoted by V OX Y, and constitutes the setof velocities for X that would result in a collision with Yat some time before τ . By definition, agents X and Y areguaranteed to be collision-free for at least time τ , if vX τ vY / V OX Y[3]. More formally,τV OX Y { v t [0, τ ] :: p X t( vX vY ) M }, (3)where t 0 and M denotes the Minkowski Sum of X andY.In general, let V denote the set of all velocities foran agent. At each simulation step, the agent must choosea velocity v new V s.t. v new lies outside the velocityobstacles defined by all the neighboring agents and obstacles,which is a sufficient condition for collision-free navigationfor at least time τ .In the case of disc-shaped agents, the Minkowski Sumfor two agents can be implicitly computed with a fewfloating point operations. Finding the closest point on adisc from a query point is also trivial. For elliptical agents,these operations are non-trivial. Computing the MinkowskiSum requires either computing convolution curves, whichis considerably more expensive [30], or using a closedform implicit equation [11]. Moreover, computing the closestpoints on two arbitrarily oriented ellipses requires computingthe roots of a fourth-order polynomial. These operations arecostly, so we present faster algorithms based on conservativelinear approximations.C. APPROXIMATING ELLIPSESInstead of computing the exact Minkowski Sum of twoellipses, we use a piece-wise linear approximation (PL) thatcan provide conservative guarantees for collision avoidance.For an ellipse C, a piece-wise linear approximation can becomputed by uniformly sampling C at intervals of δθ (0, 90) to yield the set of sample points S {(smaj cos(δθ i), smin sin(δθ i) : 0 i b 2πδθ c i I}.Let L {λp p S} denote the set of tangents to the curveC, defined at each sample point as:0λp C( p) tC ( p) p S,(4)where t 0. We can now define the set of vertices V of thebounding polygon by solving λp A λp A 1 i.e., the pointof intersection of two tangents where p A , p A 1 S.Thecomputational cost is thus O(m) for m samples. Next, weuse this property to show that the linear approximationcomputes a conservative shape for collision avoidance.Theorem 1:For any ellipse C, a piecewise linearapproximation L of the curve defined by the tangents at thesampled points overestimates the curve.Proof: Let C denote an axis-aligned ellipse defined at theorigin as:x2y2 1,(5)a2b2where a2 b2 and a, b R . The first and second derivativeof the curve, C and C resp., are given by:dyb2 x 2 ,dxa yb4d2 y. dx2a2 y 3It follows that:(C 0C 0(6)(7)if y 0,if y 0.By definition, C is concave downward for y 0, whichimplies that the tangent lines λp L lie above the curvewhen p lies in the first or second quadrant. Similarly, C isconcave upward for y 0, which implies that the tangentlines λp L lie below the curve in the interval when plies in the third or fourth quadrant. Hence, the linearizationL overestimates the curve C. Without loss of generality, thesame proof can be used for oriented ellipses.Theorem 2: We are given an ellipse C in the form y C(x) and a piecewise linear approximation L of the curvedefined by the tangents at the ordered set of samples S. LetλA L denote a linearization centered at p A (xA , C(xA ))that approximates the curve in the interval I ( pA , p j )where p A (xA , C(xA )) and p j (xj , C(xj )). Then theerror bounding function B(t) over I can be given by :B(xs ) K(1 x2s 3/2a2 ),(8)b(x x )2jAand xA xS xj . Furthermore,where K 2a2the maximum approximation error, Emax , can be exactlycomputed.Proof: As before, let us consider an axis-aligned ellipsedefined at the origin. We also assume that the set of samplesS includes the points where y 0. Let E(xj ) represent theapproximation error for point (xj , C(xj )), which is expressedas:E(xj ) C(xj ) λA x xjλA x xj C(xj ) xj R(9)(T heorem1) E(xj ) 0(10)(11)It can be proven that there is some xs I such that: s)C(x(xj xA )2 .(12)2We can derive an expression for the error-bounding function using 5 , 7, & 11, as:E(xj ) B(xs ) E(xj ) K(1 x2s 3/2a2 )(13)Differentiating B(xs ) gives:Ḃ(xs ) 3Ka2 (1 x2s 52a2 )xs .(14)It follows that the error bound is monotonically increasingwhen xs 0 i.e. xA , xj R . Similarly, it is monotonically
decreasing when xs 0 i.e. xA , xj R . Thus themaximum approximation error, Emax , over the open intervalI ( pA , p j ) can be expressed as: 3K if xA , xj R , a2 (1 x2s ) 25 xs2axs xjEmax 3K if xA , xj R . 5 xsx2 sa2 (1 a2 ) 2xs xAD. VELOCITY OBSTACLES FOR ELLIPTICAL AGENTSIn this section, we extend the ORCA algorithm [2] toelliptical agents based on the linear approximation. We referto the new algorithm as ERVO.1) Computing Neighboring Agent Constraints: To compute the velocity obstacle for an elliptical agent, we firstcompute a tangent from the origin of the velocity space to theboundaries of the Minkowski Sum scaled by the inverse of τ .For a Minkowski Sum with m samples, we can find tangentsin O(lg(m)) using binary search on the vertices. The forwardface of the truncated cone lies between the tangent points,and the nearest point can be computed by another binarysearch. Fig 1(A, B) illustrates the construction of the velocityobstacle of the elliptical agents using the Minkowski Sumand the tangents.Next, we use the velocity obstacle to compute the set ofpermitted velocities for an agent. Given the velocity obstacle,τV OX Y, we construct the set of permitted velocities for Xfor reciprocal collision avoidance [2], which is denoted asERVOτX Y . Consider a vector u from the relative velocity vX vY to the nearest point on the truncated velocityobstacle. Also, let n be the outward normal of the boundaryτof V OX Yat point ( vX vY ) u. We assume that allagents use the same collision-avoidance strategy. Therefore,agent X is responsible for adapting its velocity by 21 uassuming that Y will do the same. In this manner, the setτERV OX Yof permitted velocities for X is defined by thehalf-plane pointing in the direction of n centered at the point vX 12 u (see Fig 1(C)). Hence, one half-plane constraint isconstructed for each neighboring agent.2) Computing Neighboring Obstacle Constraints: Without loss of generality, we can assume that all obstacles in thescene are triangulated and their projections on the 2D planeare given as a collection of line segments. To compute theτvelocity obstacle V OX Ofor agent X induced by a line segment O, we implicitly compute the Minkowski Sum of Xand O scaled by the inverse of τ . An agent X will collidewith obstacle O within the time τ if its velocity vX is insideτV OX O. Geometrically, the Minkowski Sum is equivalent tosliding the reflected A along the scaled line segment (eachscaled by τ ). Because discs are unaffected by orientationissues, the computations related to determining the shape ofthe velocity obstacle, finding tangents, and determining theclosest point on the obstacle can be implemented by usinga small number of floating point operations. With ellipticalagents, the shape of the velocity obstacle, the tangents, andthe nearest point operations are governed by the orientationof the agent as well as of the obstacle.Let θ [0, 2π] represent the angle between O and thepositive x-axis. We can simplify the computation by rotatingthe coordinate system by θ, i.e., we rotate O and agent X byθ and compute the appropriate constraints in the transformedspace. Let orotX denote the orientation of the ellipse after therotation transformation. For the remainder of this section,we can assume that O is parallel to the positive x-axis.Therefore, the shape of the velocity obstacle depends only onthe orientation orotX of the agent. We can also accelerate thecomputation of tangents and the closest points (Section IV).Once rotated, we determine whether the agent’s velocityprojects onto the left tangent, right tangent, left face, rightface, or line segment. Next, we compute the point FX O onthe velocity obstacle closest to vX . The half plane definedusing the tangent to the velocity obstacle at FX O yields theset ERVOτX O of permitted velocities for X with respect toO (Figure 1(E)). We rotate the final computed constraint by θ to transform back into the original space(Figure 1(F )).3) Choosing a Collision-free Velocity: At every simulation step, we construct the half-plane constraints for eachneighboring agent and obstacle. The set of neighboringagents and obstacles can be computed efficiently by using aspatial data structure, such as a kD-tree. The set of permittedvelocities for agent X is simply the convex region – ERVOτX– given by the intersection of the half-planes of the permittedvelocities that are induced by all the neighboring agents andobstacle(Figure 1(F )).\ERVOτX Y(15)ERVOτX Y 6 XnewThe agent is responsible for selecting a new velocity vXτfrom ERVOX that minimizes the deviation from its preferred0.velocity vXnew0 vX arg min k v vXk(16)τ v ERVOXEq. 15 and 16 can be solved efficiently with an expectedruntime of O(n) using linear programming, where n is thetotal number of constraints.4) Collision-free Guarantees:: If the linear programmingalgorithm can compute a feasible solution for each agent, wecan guarantee that the resulting trajectories will be collisionfree. This follows from our conservative, bounding linear approximation (Section 3.2.1) for each ellipse. Furthermore, weextended the original ORCA algorithm [2] to elliptical agentsby formulating appropriate constraints (Sections 3.2.2 and3.2.3) that preserve the properties of the velocity obstacles.The set of permitted velocities ERV OτX Y and ERV OτY Xfor agents X and Y , respectively, are reciprocally maximal. The overall approach is conservative, but it guaranteescollision-free navigation. In densely packed conditions, theERVO set of feasible velocities may be empty, in which casethe 2D linear program will not find a solution. One possibilityis to change the orientation of the ellipses (see ERVO-F inSection V) to find a solution. If that does not find a feasiblesolution, we can select the velocity that minimally penetratesthe constraints generated by neighboring robots, by using 3Dlinear programming [2].
VYPYuτX Y2VX-VYVXuVY(B)(C)ERVO X WτPOVXERVO τX OτO X PERVτERVO X ZPXPO - PXτM(A)VOA ceFaVYPXEROτdVXPX -PYX YττERVarrwFoVXVX(D)(E)VAnew(F )Fig. 1. COMPUTING COLLISION FREE VELOCITY (A) Two agents are moving toward one another in space. The approximating polygons areshown. (B) The velocity obstacle for X induced by Y takes the shape of a truncated cone. The apex of the cone is located at the origin in velocityspace. The forward arc of the cone is the forward face of the Minkowski Sum of X and Y scaled by τ and centered at p Y p X /τ . (C) The set ofτpermitted velocities for agent X w.r.t. Y represented by the half-plane constraint ERV OX Y. (D) An agent moves toward a line segment obstacle. (E)To compute V OX O , we rotate the frame of reference such that O is parallel to the positive x-axis. In this case, the forward arc of the cone is the forwardface of the Minkowski Sum of X and O scaled by τ and centered at p O p X /τ . We also show the ERVO constraint as a half-plane perpendicularto the vector connecting vX and V OX O and passing through the nearest point on V OX O . After the constraint is computed, it is rotated back to theaxis-aligned reference frame. (F ) After all the constraints have been computed, we can determine a feasible velocity inside the union of all the ERVOsets. A new velocity is chosen from the region of feasible velocities.Fig. 2. Swept Ellipse: An ellipse (shown in black) swept along an intervalwith padding in the positive direction (in red) and negative direction (inblue) equal to the agent’s maximum angular velocity. The convex-hull ofthis swept surface (in purple) is used in place of the agent to constructMinkowski Sums and produce collision-free rotations for the ERVO-Falgorithm. A table of these swept surfaces is maintained for accelerationof the ERVO-F algorithm.IV. ACCELERATING ERVO W ITH P RECOMPUTATIONThe ERVO algorithm described above can computecollision-free trajectories for elliptical agents. However, inpractice it is computationally two orders of magnitude timesmore expensive compared to the original ORCA algorithmfor circular agents (see Table I). The main bottleneck isthe computation of the Minkowski Sum of the polygonsand determining the forward arc on its boundary whileconstructing the half-plane constraints for each neighboringagent and obstacle.In order to accelerate the computation, we use precomputed Minkowski Sums for different orientations of ellipsesand still guarantee collision-free navigation. In particular,we use a precomputed table of Minkowski Sums suchthat the runtime computation is O(1), corresponding to atable lookup. We use a discrete angular resolution of θEfor this precomputation. Let P {θE i : 0 i b θ2πc θE (0, 2π)} denotes an ordered set of angles. Also,Elet K {ROT (X(θi ), θi 1 )) θi , θi 1 P} denote theset of surfaces generated by rotating an ellipse X fromorientation θi to θi 1 for each ordered pair (θ, θi 1 ) in P.Likewise, let K0 denote the set of swept volumes (Figure 2)generated by rotating an ellipse at orientation θi by θalpha δt αmax , where δt and αmax denote the simulationtimestep and maximum angular acceleration of the robot,respectively. Each surface in K and K0 is parametrized bythe angle θi .We precompute and store the pairwise Minkowski Sumsfor surfaces in K, as well as K0 . Each such MinkowskiSum is parameterized by the corresponding pair of angles,corresponding to the two ellipses. Additionally, we alsostore the extreme points of the polygon which facilitatesthe construction of tangents and reduces the complexity offinding the closest point on the Velocity Obstacle. Consideran elliptical agent X with orientation θX . The precomputedtable can be used to find the surface KX s.t. θi θX θi 1where θi , θi 1 P. By definition, the ellipse representingthe agent X is contained within KX and is thus, conservative.When computing the constraints for two agents X and Y , welookup the surfaces KX and KY resp., and the correspondingMinkowski Sum. The collision-free guarantees (Section IIIB) still hold but the solution may not be optimal sincethe ERVO sets of collision-free velocities are not maximal.
OiPi SimajSminiPx.149Fig. 3. Narrow Passage: Two ellipses approach one another in a narrowhallway. In order to pass safely, each ellipse must rotate to reduce theirprofile. These behaviors are not possible with disc-based agents and aredemonstrated with our ERVO-F algorithm.Overall, our precomputed structures with an interval size of5 degrees provide a 40x improvement in performance. Theprecomputation time is on the order of minutes and spatialcomplexity is O(m o2 ) where m is the number of sampleson the ellipse and o is the number of orientation intervals( 120M B for o 72, m 100).V. ORIENTATION UPDATEThe use of ellipses increases the configuration space ofeach to three dimensions - [x, y, θ]. In order to maintaininteractive simulation, we decompose the problem in twoparts: update the orientation of each ellipse and computethe optimal collision-free velocity for that orientation. Byusing swept surfaces in place of rotating ellipses for theconstruction of neighboring agent constraints, we ensurecollision-free rotations as agents navigate. Figure 2 illustratesthe swept surfaces. We present two simple approaches toorientation computation, given as function definitions H, fororientation update: ERVO-C: In the simplest case, the agents maintain theirorientation between successive simulation time-steps:o0i oi . (17)ERVO-F: In some cases, the agent must change itsorientation in order to find a collision-free velocity.For example, in Figure 3, the agent must change itsorientation to navigate through a narrow hallway. In thismethod, we determine whether agent i can travel alongits current velocity vi with its current orientation oi byestimating the scalar space, ci , available to the agentw.r.t its current orientation at a point slightly ahead inthe direction of travel. Let MC(o) denote the minimumclearance required for an agent with orientation o. Then,o0i is given by:(oi if ci MC(oi ),0oi oEotherwise.iwhere oEi denotes closest orientation to oi such that ci MC(oEi ). Clearance can be computed as the distanceto the nearest point on the nearest neighboring agent orobstacle from the extreme point on either side of theagent with respect to its velocity.Simulation Update At each time step, we evaluate H andK (Section IV) to determine the preferred orientation o0 andOiPi SimajSmini.135.22.2286Fig. 4. Bounding Disc vs Ellipse. Disc (Blue) and ellipse (Brown) for(Left) a human of average body width and depth; (Right) HRP-4 robot.preferred velocity v 0 for robot. Next, we compute the ERVOconstraints (Section III-D) using “swept” surfaces from theset K0 for agents for which o 6 o0 and the less conservativesurfaces from the set K for the remaining ones. The agentsfor which the 2D linear program computes a feasible solutioncan update their orientation. The remaining robots maintaintheir orientation and we use 3D linear programming tocompute the “safest possible” velocity.VI. RESULTSIn this section, we highlight the performance of ouralgorithm on several planar navigation benchmarks (Figure 5). We model a human body with average width anddepth (smaj .2286, smin .149, r .2286) for ourexperiments, and an HRP-4 humanoid robot (smaj .22,smin .135, r .22) for the crossflow scenario.We set the sampling size at m 100 points for ourpiece-wise linear approximation and orientation intervalsof 5 degrees for precomputed surfaces. Using Theorem 2(Section III-C), the maximum approximation error for apoint on the bounding ellipse for a human was found to be0.005. The aggregate error, defined as the difference betweenthe area of the exact ellipse and approximated ellipse, was0.0002m2 .We implemented our algorithm in C on a windows 7desktop PC. Timing results (Table I) were generated on anIntel i7-4790 pc with 16GB of ram. Although both ERVOand ORCA can be parallelized, results were generated on asingle core.A. ERVO Performance: Benefit of Pre-computationWe have evaluated the performance of the ERVO al
robot or agent from its start position to its goal position. This problem arises not only in robotics and AI, but also in computer games, virtual environments, pedestrian dynamics, and simulations of collective behaviors in biology. In this paper, we mainly address the problem of real-time multi-agent collision avoidance for large environments with
Reciprocal n-body Collision Avoidance Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha Abstract In this paper,we present a formal approachto reciprocal n-bodycollision avoidance, where multiple mobile robots need to avoid collisions with each other while movingin a commonworkspace.In our formulation,each robotacts fully in-
collisions in the networks such as ALOHA, CSMA, MACA and MACAW. MACAW Protocol Multiple Access with Collision Avoidance for Wireless (MACAW) is a widely used MAC sub layer protocol. MACAW is useful for mobile ad-hoc networks. It contains new collision avoidance mechanisms. By these me-chanisms data transmission is completed in five steps.
With more than 10,000 TCAS II/ACAS II installations on more than 325 aircraft types, Honeywell is the overwhelming choice in collision avoidance for airline and corporate pilots. Honeywell now combines the unmatched flexibility of Integrated Hazard Avoidance System with
collision avoidance and compliance with the rules of COL-REGS, using velocity and line-of-sight vectors to express the COLREGS rules. The constraints are implemented as penalties in order to ensure that the best possible control behavior can be chosen also when collision with at least one obstacle seems unavoidable. II. SYSTEM OVERVIEW
multi-robot systems. For example, consider the problem of building an automatic collision avoidance system (ACAS) for aerial robots that would scale up as the autonomous aerial traffic increases. Such a system needs to be computationally efficient for execution in real-time and robust to various real-
5 1. Collision Physics – An Overview. 1.1 Outline. Collision physics includes ANY collision of a quantum particle with a target. Collision Particles may be: PHOTONS (eg from a Laser, Synchrotron source or FEL) ELECTRONS (usually of well defined momentum from an electron gun) IONS (usually from an ion source of well defin
Probate Avoidance, Deed Choices for WV Real Estate, and Appraisement and Inventory MARCH 24, 2021 - Webinar Host: The WV State Bar Probate Law Committee CLE: 3 CLE credits Time: 1:00 pm. to 4:00 p.m. Speakers: J. E. White - Probate Avoidance Christopher J. Winton - Deed Choices for WV Real Estate
The Adventures of Tom Sawyer 4 of 353 She went to the open door and stood in it and looked out among the tomato vines and ‘jimpson’ weeds that constituted the garden. No Tom. So she lifted up her voice at an angle calculated for distance and shouted: ‘Y-o-u-u TOM!’ There was a slight noise behind her and she turned just
