Detection, Prediction, And Avoidance Of Dynamic Obstacles .

3y ago
27 Views
2 Downloads
1.27 MB
6 Pages
Last View : 27d ago
Last Download : 3m ago
Upload by : Luis Wallis
Transcription

Detection, Prediction, and Avoidance of Dynamic Obstacles in UrbanEnvironmentsDave Ferguson, Michael Darms, Chris Urmson, and Sascha KolskiAbstract— We present an approach for robust detection,prediction, and avoidance of dynamic obstacles in urban environments. After detecting a dynamic obstacle, our approachexploits structure in the environment where possible to generatea set of likely hypotheses for the future behavior of the obstacleand efficiently incorporates these hypotheses into the planningprocess to produce safe actions. The techniques presentedare very general and can be used with a wide range ofsensors and planning algorithms. We present results from animplementation on an autonomous passenger vehicle that hastraveled thousands of miles in populated urban environmentsand won first place in the DARPA Urban Challenge.Fig. 1. Our autonomous vehicle “Boss” during vehicle interaction testingin Pittsburgh, Pennsylvania.I. INTRODUCTIONDriving in urban environments requires interacting withother vehicles. Whether following behind a slow-movingvehicle, coordinating to take turns with vehicles at intersections, or maneuvering around other vehicles to reach parkingspots, it is near impossible to take any voyage in a car withoutbeing affected by another vehicle in some manner. As driverassistance systems and autonomous vehicles become moresophisticated, reasoning about such vehicle interactions willbecome increasingly important. To do so, three capabilities are required. First, other vehicles must be reliablydetected, through on-board or off-board sensors or vehicleto-vehicle communication. Secondly, the future behavior ormovement of these vehicles must be imparted or inferred.And finally, this information must be used to provide safe,intelligent courses of action for the driver assistance systemor autonomous vehicle. Although much research has beenperformed in these areas, particularly for robotic systems,current approaches fail to satisfy the requirements of generalurban driving.For dynamic obstacle detection, the configuration of sensors is dependent on the application [1]. Traditional configurations for commercial driver assistance systems couplea single sensor to a tracking model which is in turn tiedto a particular application (for instance Adaptive CruiseControl [2]). However, driving in an urban environment withThis work would not have been possible without the dedicated effortsof the Tartan Racing team and the generous support of our sponsorsincluding General Motors, Caterpillar, and Continental. This work wasfurther supported by DARPA under contract HR0011-06-C-0142.D. Ferguson is with Intel Research Pittsburgh and Carnegie Mellon University, Pittsburgh, PA, USA. Email: dave.ferguson@intel.comM. Darms is with Continental Inc., Auburn Hills, MI, USA. Email:michael.darms@us.contiautomotive.comC. Urmson is with Carnegie Mellon University, Pittsburgh, PA, USA.Email: curmson@ri.cmu.eduS. Kolski is with ETHZ, Zürich, Switzerland. Email:sascha.kolski@mavt.ethz.charbitrary road shapes and open areas requires a more generalframework for modeling and tracking vehicles.Further, no single sensor exists that fulfills the requirements for reliable dynamic obstacle detection in urban environments. Strong empirical evidence of this comes from theUrban Challenge Final Event where all of the autonomousvehicles relied on multiple sensors in their perception systems [3]. Unfortunately, using multiple heterogenous sensorsincreases the complexity of the sensor fusion task, since eachsensor has different characteristics that need to be consideredto combine their results effectively (see, for example, [4]).For dynamic obstacle prediction, the simplest approach isto assume that the obstacles remain in their current positionsforever and treat them as static. Existing approaches that dotreat them as moving often require perfect information abouttheir trajectories [5], [6] or assume they will continue alongtheir current heading and velocity [7], [8], [9]. However, inpractice none of these scenarios are realistic: it is unlikely wewill have accurate information from another vehicle as to itsfuture trajectory, nor in general will it just continue along itscurrent heading (or stop and sit still). Recently, researchershave extended these approaches to incorporate a notion ofuncertainty in the future behavior of other vehicles throughprobabilistic trajectory models, but these too are heavilybiased towards the vehicles continuing their exact currentbehavior [10]. Sometimes, such models are the best we cando as we have no additional information to draw upon, butin structured environments such as roads and intersectionswe can exploit this structure to generate much more realisticpredictions for the future movement of other vehicles.Research into generating safe actions amongst moving vehicles has traditionally focused on very simple environmentsand simple vehicle models [11], [12], [13], or very shortterm (often instantaneous) actions [8], [9]. However, effectivedriving in urban environments can require complex actions

(a) Road Structure(b) Static Obstacle MapFig. 2.Fig. 3.(c) Dynamic Obstacle ListDifferent Outputs from PerceptionPerception Architecture.and non-trivial vehicle models. Further, the number of othervehicles that must be modeled to ensure an action is safeand reasonable can be very large and so efficient methods ofreasoning about this interaction are required.In this paper, we describe an approach for reliable detection, prediction, and avoidance of dynamic obstacles inboth on-road and unstructured areas of urban environments.The resulting approach is robust to real-world sensor noise,exploits structure in the environment for realistic predictionof vehicle behavior, and ensures that selected actions arefeasible. Further, the approach is general enough to use witha wide range of sensors, vehicle models, and path planners.We also describe an example implementation of the approachon “Boss”, Carnegie Mellon University’s autonomous vehicleentry into the DARPA Urban Challenge, where it has beenemployed for over 3000 kilometers of autonomous urbandriving and contributed to a first place finish in the competition.intersections in the environment (in our case, in a vectorformat – see Fig. 2(a)). This information can be obtainedfrom prior data (such as aerial imagery) and processed inan offline manner or obtained through onboard perception.In our system, we fused both sources to provide an accuratedescription of the road in the vicinity of the vehicle.Our static obstacle map representation is a twodimensional grid (see Fig. 2(b)). Once a dynamic obstacle listis generated, care is taken to remove the dynamic obstaclesfrom this map so that they are not duplicated.The instantaneous map is very similar to the static obstaclemap, but contains all obstacles, static and dynamic. Nodistinction is made between the two classes and this mapis used for target validation in the sensor fusion system fordynamic obstacle detection.The dynamic obstacle list provides information about allobstacles around the vehicle that are potentially moving.Our dynamic obstacle detection approach represents eachdynamic obstacle by an estimation of its shape and its currentdynamic properties (see Fig. 5). While our architecturecan incorporate an arbitrary number of models, for thisapplication, the shape of each obstacle is one of two models:a box model and a point model (see also [14]).II. DYNAMIC OBSTACLE DETECTIONBoss’ perception system provides four principle pieces ofinformation: a vectorized road structure, a static obstaclemap, an instantaneous obstacle map and a dynamic obstaclelist. Because the dynamic obstacle list is influenced by,and itself influences, the other perceptual outputs we brieflydescribe all these components.The road structure is a representation of the lanes and(a) Box ModelFig. 5.(b) Point ModelDifferent Dynamic Obstacle Shape Models.The box model represents the shape of a vehicle while thepoint model contains no shape information. The point model

Fig. 4.Detecting dynamic obstacles traveling on roads.is used when sensor data does not support the box modelor when a box representation does not match the featuresextracted from raw sensor data.For the box model the velocity and acceleration vectorsare always parallel to the longer edge. The orientation isdescribed by an angle φ and an angular rate φ̇. The statepropagation equations couple the x and y coordinates viathe angle φ and angular rate φ̇ through a simple bicyclemodel (see e.g. [15]). The point model is described bytwo coordinates in the 2D plane and the correspondingvelocities and accelerations. For the point model, a constantacceleration model with a gaussian noise component basedon the current direction of travel is used for state propagation(see e.g. [16]).The use of these fixed shape models significantly reducesthe complexity of the fusion algorithm (see [14]). In contrastto algorithms using an adaptive or flexible shape modelthese models do not necessarily represent the actual shapeof the tracked object. However, aligning the model with theclosest point to our vehicle in general gives a worst caseestimation of the position of the tracked vehicle relative toBoss. Empirically, extensive testing showed this approach tobe sufficient for on road driving and driving in open parkinglots.To reliably detect dynamic obstacles we use a multisensor approach combining radar and laser data from different sensors and sensor technologies. For every sensor atype dependent sensor module is used (see e.g. [17]). Eachsensor extracts a set of features and associated them to thecurrent set of dynamic obstacle hypotheses. For example,laser scanner data is processed to extract “L” shaped cornerfeatures that could correspond to vehicles.Each feature is first validated by a sensor specific algorithm. As an example, for features from a radar sensor, thevelocity measured by Doppler shift can be used. Next, thefeatures are checked against the instantaneous obstacle mapand the road shape to reject false positives (e.g. artifactscaused by ground detections).Remaining features are then fused into a set of box andpoint dynamic obstacles. Each sensor module proposes aninterpretation of the extracted feature for the best trackingmodel and a voting algorithm selects the best model forobject tracking. Fig. 4 provides an example of the approachin action during an Urban Challenge qualification run. Here,the first image shows the corner features extracted froma planar laser sensor and the second image shows thesefeatures being evaluated against the instantaneous obstaclemap (map shown in red) and the road. The third image showsthe resulting box and point object hypothesis that best explainthe sensor data.Fig. 6.Different Dynamic Obstacle Velocity Models.To differentiate between objects that have always beenstatic and may remain static (e.g. parked cars), vehicles thathave been moving but are currently stopped (e.g. cars atan intersection), and vehicles that are currently moving, allobject hypothesis are further classified into a) Moving andNot Moving and b) Observed Moving and Not ObservedMoving (see Fig. 6). The Moving flag is set if the objectcurrently has a velocity that is significantly different thanzero. The Observed Moving flag is set when the object hasbeen observed to be moving for a significant amount of timeand is cleared when the object has not been detected movingfor a prolonged period of time. These durations vary basedon the certainty with which the object has been classified asmoving.The consideration of the Moving and Observed Movingobstacle characteristics removes the need for traditional clas-

(a) Predicting future on-road behaviorFig. 7.(b) Predicting future on-road and parking lot behaviorPredicting the future behavior of other vehicles on roads and in parking lots.sification and recognition of vehicles (see e.g. [18]). Further,it allows the planning system the opportunity to treat eachof these obstacle classes differently. We also use these flagsto decide which of the detected obstacles should be removedfrom the static obstacle map. Specifically, if an obstacle doesnot have the Observed Moving flag set, we leave it in thestatic obstacle map and do not treat it as a dynamic obstacleduring planning.III. DYNAMIC OBSTACLE PREDICTIONIf an obstacle has been detected as moving, it is importantto predict its future motion so that actions can be selectedthat are safe through time. In general, this prediction problemis extremely difficult, as we do not have control over theseother objects so knowing exactly where they intend to goand how they intend to get there is impossible. However,when these dynamic obstacles are vehicles operating inurban environments, it is much easier to infer their likelybehavior through exploiting the structure inherent in suchenvironments.The basic idea is quite simple: vehicles traveling on roadstypically follow common rules of the road. For instance,a vehicle driving along a road is most likely to continuedriving along the road, and a vehicle at an intersection islikely to choose to travel down one of the roads availableat the intersection. This simple idea allows us to generatehypotheses for where a particular vehicle will travel in thefuture, based on its current behavior and the structure of theenvironment.To implement this idea, we first take the detected dynamicobstacle and its position, heading, and velocity. The boxmodel provides an explicit heading estimate, while the pointmodel provides an implicit heading based on the object’svelocity. We then take a model of the road structure in thevicinity of the dynamic obstacle and determine which roadlane(s) it is currently traveling in. We use the position andheading of the dynamic obstacle to calculate what its currentoffset is from that lane (i.e. whether it is currently travelingdown the center of the lane or is biased to one side). Wethen hypothesize that the dynamic obstacle will continue totravel down the lane and will likely maintain the same offsetthat it currently has. However, if the dynamic obstacle isnot heading directly down the lane we predict that it willchange its heading over time to align itself with the lane.For instance, if a vehicle is entering onto a road it is likelyit will align itself with the road.To provide accurate predictions leading up to intersectionsand stop-lines, we reason about the future speed of thedynamic obstacle as well as its course. A dynamic obstaclethat is approaching a stop-line is predicted to slow down andstop at the stop-line.If a dynamic obstacle is at or approaching an intersection,we generate multiple hypotheses of where it could go. Todo this, we calculate all the possible lanes that it couldleave the intersection from and generate hypotheses foreach of them using the above approach. Admittedly, thisprovides a conservative prediction of the future behavior ofthe vehicle (obviously, it could only actually travel downone of these lanes), but because intersections are typicallyprone to confusion and accidents, we feel that exhibitingextra caution in these areas is prudent. Fig. 7(a) shows thepredicted behavior of the vehicles detected in Fig. 4.Generating predictions for dynamic obstacles traveling onroads is only part of the solution, however, since urbandriving also involves navigating through parking lots andopen, unstructured areas. In such scenarios, the structureof lanes and intersections doesn’t exist and thus cannot beexploited. Our approach in these areas is to extrapolate thecurrent behavior of the dynamic obstacles, similar to existingapproaches mentioned earlier.However, rather than just using the position and velocityof the dynamic obstacles to perform this extrapolation,the box model allows us to also incorporate the headingand curvature of the obstacle to provide a more accurate

Fig. 8. Following a road lane and avoiding an oncoming vehicle. Our vehicle generates a set of local trajectories down the travel lane and evaluateseach to select the best that is collision-free. The steps in the dynamic obstacle collision checking algorithm are shown performed for one of the candidatetrajectories (with the surrounding environment removed for clarity). First the worst-case bounding boxes are created for the candidate trajectory andthe dynamic obstacle trajectory. Next, since these intersect, the simple pessimistic circles are computed along the trajectories and collision-checked inchronological order. As soon as these intersect at any time frame, the accurate vehicle polygons are collision-checked. In this case, these polygons intersectso the candidate trajectory can be ruled out of contention. This hierarchical approach is equivalent to performing a full check involving the vehicle polygons(shown in the second to last image). The final image shows a different candidate trajectory that does not intersect with the dynamic obstacle and is selectedfor execution.short term prediction. For the point model, which is mainlyused for dynamic obstacles that are further away from ourvehicle, the estimated heading is incorporated but curvatureis ignored. Although this prediction model is not as accurateas the on-road model, typically the speeds employed in theseunstructured areas are much lower than those on roads, soreacting to updated predictions is much easier and thus therisks of collision are reduced. Fig. 7(b) shows this predictionfor a vehicle detected in a parking lot (as well as othersdetected on the adjacent roads).IV. DYNAMIC OBSTACLE AVOIDANCETo safely avoid dynamic obstacles we rely on a motionplanner that generates a set of candidate actions for thevehicle and selects from this set one that is collision-freewith respect to these obstacles. In our implementation eachof these actions is a dynamically-feasible trajectory that canbe directly executed by the vehicle. The length of thesetrajectories varies based on the current speed of our vehicleand is designed to ensure the vehicle could, if necessary,come to a stop over the course of the trajectory. These trajectories are generated using a model-based trajectory generatordeveloped by Howard and Kelly [19] that incorporates ahigh-fidelity vehicle model to produce an accurate predictionof the vehicle’s movement as it executes the trajectory. Wecan then use this prediction along with our dynamic obstaclepredictions to determine whether a candidate trajectory forour vehicle will cause a future collision with any of thedynamic obstacles.We perform this collision-checking efficiently using ahierarchical approach. Given a candidate trajectory for ourvehicle and a predicted trajectory for a dynamic obstacle (extended out in time to match the time duration ofthe candidate trajectory), we first construct a conservativebounding box for each trajectory. These bounding boxesrepresent a pessimistic approximation of the area of theenvironment the trajectories encounter. We then check to seeif these bounding boxes overlap: if they don’t, then the twotrajectories cannot intersect each other; if they do, then thereis a chance the trajectories intersect and we must continueto investigate. We then take the two trajectories and stepalong them in chronological, synchronized time. At eachtime instant ti we construct a pessimistic bounding circle

of the extent of our vehicle and the dynamic obstacle andcheck if these circles intersect. If we reach the end of ourtrajectory without any such intersections, the two trajectoriescannot intersect each other1 . If the circles intersect at sometime tk , then we construct accurate polygonal representationsof our vehicle and the dynamic obstacle at this time tkand check if these polygons intersect. If so, the trajectorieswill collide with each other and this candidate trajectoryis removed from contention. If not, we continue to stepforwards in time performing our pessimistic bounding circ

Detection, Prediction, and Avoidance of Dynamic Obstacles in Urban Environments Dave Ferguson, Michael Darms, Chris Urmson, and Sascha Kolski Abstract—We present an approach for robust detection, prediction, and avoidance of dynamic obstacles in urban en-vironments. After detecting a dynamic obstacle, our approach exploits structure in the environment where possible to generate a set of .

Related Documents:

The project “Obstacle Detection and Avoidance by a Mobile Robot” deals with detection and avoidance of the various obstacles found in an environment. We divided the task of creating the robot into five phases namely LED and LDR component designing, comparator, microcontroller, motor driver and the motor. While designing and construction of the

avoidance, two ethical standards were applied: the Utilitarianism approach and the Deontology approach. The former approach states that ethics of tax avoidance cannot be determined theoretically because this evaluation depends, ultimately, on the quality of the government. The latter approach states that tax avoidance is an .

This paper examines the relative valuation of alternative methods of tax avoidance. Prior studies find that firm value is positively associated with overall measures of tax avoidance; I extend this research by providing evidence that investors distinguish between methods of tax reduction in their valuation of tax avoidance.

Integrated Obstacle Detection and Avoidance in Motion Planning and Predictive Control of Autonomous Vehicles Rien Quirynen 1, Karl Berntorp , Karthik Kambam , Stefano Di Cairano Abstract—This paper presents a novel approach for ob-stacle avoidance in autonomous driving systems, based on a hierarchical software architecture that involves both a low- rate, long-term motion planning algorithm .

AS5553, Counterfeit Electronic Parts; Avoidance, Detection, Mitigation and Disposition, current version - DoD Adopted 31 Aug 2009 AS6081, Distribution Counterfeit Electronic Parts; Avoidance Protocol, Distributors, current version - DoD Adopted 10 Jun 2013 EPRI TR -1019163, Counterfeit, Fraudulent and Substandard Items,

The obstacle detection is done using Sharp distance IR sensors. After detecting the obstacle and this signal is passed to the ATmega2560 microcontroller on receiving the signals it guides the vehicle to moves in a different direction by actuating the motors through the motor driver. Keywords—Autonomous Vehicle, Obstacle Detection, Obstacle Avoidance, Sharp Distance IR sensors long range(20cm .

developing assistive technology for obstacle avoidance for visually impaired people, because it has always been con-sidered a primary requirement for aided mobility. Obstacle avoidance technology needs to address two issues: obsta-cle detection and obstacle warning. The obstacle detection means the perception of potentially hazardous objects in the environment ahead of time, while the latter .

dispenser control, car wash control, and fast food transactions. Like the Ruby SuperSystem and the Topaz, the Ruby2 accepts and processes all payment options, including cash, checks, credit and debit cards, coupons, and various prepaid cards. The Ruby2 has a 15-inch touch screen and a color display. Online help is