Robotic Motion Planning: Bug Algorithms
Robotic Motion Planning:Bug AlgorithmsRobotics Institute 16-735http://www.cs.cmu.edu/ motionHowie Chosethttp://www.cs.cmu.edu/ choset16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
What’s Special About Bugs Many planning algorithms assume global knowledge Bug algorithms assume only local knowledge of the environmentand a global goal Bug behaviors are simple:– 1) Follow a wall (right or left)– 2) Move in a straight line toward goal Bug 1 and Bug 2 assume essentially tactile sensing Tangent Bug deals with finite distance sensing16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
A Few General Concepts Workspace W– ℜ(2) or ℜ(3) depending on the robot– could be infinite (open) or bounded (closed/compact) Obstacle WOi Free workspace Wfree W \ iWOi16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
The Bug AlgorithmsInsect-inspiredprovable results. known direction to goal robot can measuredistance d(x,y) betweenpts x and yGoal otherwise local sensingwalls/obstacles & encoders reasonable world1) finitely many obstaclesin any finite area2) a line will intersect anobstacle finitely many times3) Workspace is boundedW Br(x), r Br(x) { y ℜ(2) d(x,y) r }Start16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Buginner Strategy“Bug 0” algorithm known direction to goal otherwise local sensingwalls/obstacles & encodersSome notation:qstart and qgoal“hit point” qHi“leave point qLiA path is a sequence of hit/leavepairs bounded by qstart and qgoal16-735, Howie Choset with slides from G.D. Hager and Z. Doddshow ?
Buginner Strategy“Bug 0” algorithm known direction to goal otherwise local sensingwalls/obstacles & encoders1) head toward goal2) follow obstacles until you canhead toward the goal again3) continue16-735, Howie Choset with slides from G.D. Hager and Z. Doddspath ?
Buginner Strategy“Bug 0” algorithm1) head toward goal2) follow obstacles until you canhead toward the goal again3) continueassume a leftturning robotThe turning direction mightbe decided beforehand 16-735, Howie Choset with slides from G.D. Hager and Z. DoddsOK ?
Bug ZapperWhat map will foil Bug 0 ?“Bug 0” algorithm1) head toward goal2) follow obstacles until you canhead toward the goal again3) continue16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Bug ZapperWhat map will foil Bug 0 ?“Bug 0” algorithm1) head toward goal2) follow obstacles until you canhead toward the goal again3) continuegoalstart16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
A better bug?But add some memory! known direction to goal otherwise local sensingwalls/obstacles & encoders16-735, Howie Choset with slides from G.D. Hager and Z. Doddsimprovement ideas?
Bug 1But some computing power! known direction to goal otherwise local sensingwalls/obstacles & encoders“Bug 1” algorithm1) head toward goal2) if an obstacle is encountered,circumnavigate it and rememberhow close you get to the goal3) return to that closest point (bywall-following) and continueVladimir Lumelsky & Alexander Stepanov: Algorithmica 198716-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Bug 1But some computing power! known direction to goal otherwise local sensingwalls/obstacles & encoders“Bug 1” algorithm1) head toward goal2) if an obstacle is encountered,circumnavigate it and rememberhow close you get to the goal3) return to that closest point (bywall-following) and continueVladimir Lumelsky & Alexander Stepanov: Algorithmica 198716-735, Howie Choset with slides from G.D. Hager and Z. Dodds
BUG 1 More formally Let qL0 qstart; i 1 repeat– repeat from qLi-1 move toward qgoal– until goal is reached or obstacle encountered at qHi– if goal is reached, exit– repeat follow boundary recording pt qLi with shortest distance to goal––––until qgoal is reached or qHi is re-encounteredif goal is reached, exitGo to qLiif move toward qgoal moves into obstacle exit with failure– else i i 1 continue16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
“Quiz”Bug 1 analysisBug 1: Path BoundsWhat are upper/lower bounds on thepath length that the robot takes?D straight-line distance from start to goalPi perimeter of the i th obstacleLower bound:What’s the shortestdistance it might travel?DP2Upper bound:What’s the longestdistance it might travel?P1What is an environment where your upper bound is required?16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
“Quiz”Bug 1 analysisBug 1: Path BoundsWhat are upper/lower bounds on thepath length that the robot takes?D straight-line distance from start to goalPi perimeter of the i th obstacleLower bound:What’s the shortestdistance it might travel?DDP2Upper bound:What’s the longestdistance it might travel?D 1.5 Σ PiiP1What is an environment where your upper bound is required?16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
How Can We Show Completeness? An algorithm is complete if, in finite time, it finds a path if such a pathexists or terminates with failure if it does not. Suppose BUG1 were incomplete– Therefore, there is a path from start to goal By assumption, it is finite length, and intersects obstacles a finite number of times.– BUG1 does not find it Either it terminates incorrectly, or, it spends an infinite amount of time Suppose it never terminates– but each leave point is closer to the obstacle than corresponding hit point– Each hit point is closer than the last leave point– Thus, there are a finite number of hit/leave pairs; after exhausting them, the robot willproceed to the goal and terminate Suppose it terminates (incorrectly) Then, the closest point after a hit must be a leave where it would have to move intothe obstacle– But, then line from robot to goal must intersect object even number of times (Jordan curvetheorem)– But then there is another intersection point on the boundary closer to object. Since weassumed there is a path, we must have crossed this pt on boundary which contradicts thedefinition of a leave point.16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Another step forward?Call the line from the startingpoint to the goal the m-line“Bug 2” Algorithm16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
A better bug?Call the line from the startingpoint to the goal the m-line“Bug 2” Algorithm1) head toward goal on the m-line16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
A better bug?Call the line from the startingpoint to the goal the m-line“Bug 2” Algorithm1) head toward goal on the m-line2) if an obstacle is in the way,follow it until you encounter them-line again.16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
A better bug?m-line“Bug 2” Algorithm1) head toward goal on the m-line2) if an obstacle is in the way,follow it until you encounter them-line again.3) Leave the obstacle and continuetoward the goal16-735, Howie Choset with slides from G.D. Hager and Z. DoddsOK ?
A better bug?“Bug 2” Algorithm1) head toward goal on the m-lineStart2) if an obstacle is in the way,follow it until you encounter them-line again.3) Leave the obstacle and continuetoward the goalGoal16-735, Howie Choset with slides from G.D. Hager and Z. Dodds NO! How do we fix this?
A better bug?“Bug 2” Algorithm1) head toward goal on the m-lineStart2) if an obstacle is in the way,follow it until you encounter them-line again closer to the goal.3) Leave the obstacle and continuetoward the goalGoalBetter or worse than Bug1?16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
The Spiral16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
BUG 2 More formally Let qL0 qstart; i 1 repeat– repeat from qLi-1 move toward qgoal along the m-line– until goal is reached or obstacle encountered at qHi– if goal is reached, exit– repeat follow boundary– until qgoal is reached or qHi is re-encountered orm-line is re-encountered, x is not qHi, d(x,qgoal) d(qHi,qgoal) and wayto goal is unimpeded– if goal is reached, exit– if qHi is reached, return failure– else qLi m i i 1 continue16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
head-to-head comparisonor thorax-to-thorax, perhapsDraw worlds in which Bug 2 does better than Bug 1 (and vice versa).Bug 2 beats Bug 1Bug 1 beats Bug 216-735, Howie Choset with slides from G.D. Hager and Z. Dodds
head-to-head comparisonor thorax-to-thorax, perhapsDraw worlds in which Bug 2 does better than Bug 1 (and vice versa).Bug 2 beats Bug 1Bug 1 beats Bug 2?16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
head-to-head comparisonor thorax-to-thorax, perhapsDraw worlds in which Bug 2 does better than Bug 1 (and vice versa).Bug 2 beats Bug 1Bug 1 beats Bug 216-735, Howie Choset with slides from G.D. Hager and Z. Dodds
BUG 1 vs. BUG 2 BUG 1 is an exhaustive search algorithm– it looks at all choices before commiting BUG 2 is a greedy algorithm– it takes the first thing that looks better In many cases, BUG 2 will outperform BUG 1, but BUG 1 has a more predictable performance overall16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
“Quiz”Bug 2 analysisBug 2: Path BoundsWhat are upper/lower bounds on thepath length that the robot takes?D straight-line distance from start to goalPi perimeter of the i th obstacleLower bound:What’s the shortestdistance it might travel?DUpper bound:What’s the longestdistance it might travel?What is an environment where your upper bound is required?16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
“Quiz”Bug 2 analysisBug 2: Path BoundsWhat are upper/lower bounds on thepath length that the robot takes?D straight-line distance from start to goalPi perimeter of the i th obstacleLower bound:What’s the shortestdistance it might travel?Upper bound:What’s the longestdistance it might travel?DD Σini # of s-line intersections of theni2Pii th obstacleWhat is an environment where your upper bound is required?16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
“Quiz”Bug 2 analysisBug 2: Path BoundsWhat are upper/lower bounds on thepath length that the robot takes?D straight-line distance from start to goalPi perimeter of the i th obstacleLower bound:What’s the shortestdistance it might travel?Upper bound:What’s the longestdistance it might travel?DD Σini # of s-line intersections of theto ni2Pii th obstacleWhat is an environment where your upper bound is required?16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
A More Realistic Bug As presented: global beacons plus contact-based wall following The reality: we typically use some sort of range sensing devicethat lets us look ahead (but has finite resolution and is noisy). Let us assume we have a range sensor16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Raw Distance FunctionSaturated raw distance function16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Intervals of Continuity Tangent Bug relies on finding endpoints of finite, conts segmentsof ρR16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Motion-to-Goal Transitionfrom Moving Toward goal to “following obstalces”TransitionCurrently, the motion-to-goal behavior “thinks” the robot can get to the goalNow, it starts to see something --- what to do?Ans: For any Oi such that d(Oi,qgoal) d(x,qgoal),choose the pt Oi that minimizes d(x,Oi) d(Oi,qgoal)16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Minimize Heuristic ExampleAt x, robot knows only what it sees and where the goal is,so moves toward O2. Note the lineconnecting O2 and goal pass throughobstacleso moves toward O4. Note some“thinking” was involved and the lineconnecting O4 and goal pass throughobstacleFor any Oi such that d(Oi,qgoal) d(x,qgoal),choose the pt Oi that minimizes d(x,Oi) d(Oi,qgoal)16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Motion To Goal ExampleFor any Oi such that d(Oi,qgoal) d(x,qgoal),choose the pt Oi that minimizes d(x,Oi) d(Oi,qgoal)16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Transition from Motion-to-GoalChoose the pt Oi that minimizesd(x,Oi) d(Oi,qgoal)Problem: what if this distancestarts to go up?Ans: start to act like a BUG andfollow boundaryM is the point on the “sensed”obstacle which has the shorteddistance to the goalFollowed obstacle: the obstaclethat we are currently sensingBlocking obstacle: the obstaclethat intersects the segmentThey start as the same16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Transition from Motion-to-GoalChoose the pt Oi that minimizesd(x,Oi) d(Oi,qgoal)Problem: what if this distancestarts to go up?Ans: start to act like a BUG andfollow boundaryM is the point on the “sensed”obstacle which has the shorteddistance to the goalFollowed obstacle: the obstaclethat we are currently sensingBlocking obstacle: the obstaclethat intersects the segmentThey start as the sameFor any Oi such that d(Oi,qgoal) d(x,qgoal),choose the pt Oi that minimizes d(x,Oi) d(Oi,qgoal)16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Boundary FollowingMove toward the Oi on thefollowed obstacle in the “chosen”directionM is the point on the “sensed”obstacle which has the shorteddistance to the goalFollowed obstacle: the obstaclethat we are currently sensingBlocking obstacle: the obstaclethat intersects the segmentMaintain dmin and dleaveThey start as the same16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
d and dminleave dmin is the shortest distance, observed thus far, between thesensed boundary of the obstacle and the goal dleave is the shortest distance between any point in the currentlysensed environment and the goal Terminate boundary following behavior when dleave dmin Initialize with16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Example: Zero Senor Range1.2.3.4.5.6.Robot moves toward goal until it hits obstacle 1 at H1Pretend there is an infinitely small sensor range and the Oi which minimizes theheuristic is to the rightKeep following obstacle until robot can go toward obstacle againSame situation with second obstacleAt third obstacle, the robot turned left until it could not increase heuristicdmin is distance between M3 and goal, dleave is distance between robot and goal becausesensing distance is zero16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Example: Finite Sensor Range16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Example: Infinite Sensor Range16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
dmin is constantly updated16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
The Basic Ideas A motion-to-goal behavior as long as way is clear or there is avisible obstacle boundary pt that decreases heuristic distance A boundary following behavior invoked when heuristic distanceincreases. A value dmin which is the shortest distance observed thus farbetween the sensed boundary of the obstacle and the goal A value dleave which is the shortest distance between any point inthe currently sensed environment and the goal Terminate boundary following behavior when dleave dmin16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Tangent Bug Algorithm1) repeata) Compute continuous range segments in viewb) Move toward n {T,Oi} that minimizes h(x,n) d(x,n) d(n,qgoal)untila) goal is encountered, orb) the value of h(x,n) begins to increase2) follow boundary continuing in same direction as before repeatinga) update {Oi}, dleave and dminuntila) goal is reachedb) a complete cycle is performed (goal is unreachable)c) dleave dminNote the same general proof reasoning as before applies, althoughthe definition of hit and leave points is a little trickier.16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Implementing Tangent Bug Basic problem: compute tangent to curve forming boundary of obstacleat any point, and drive the robot in that direction Let D(x) minc d(x,c) c i WOiLet G(x) D(x) - W* some safe following distanceNote that G(x) points radially away from the objectDefine T(x) ( G(x)) the tangent direction– in a real sensor (we’ll talk about these) this is just the tangent to the arrayelement with lowest reading We could just move in the direction T(x)– open-loop control Better is δ x µ (T(x) - λ ( G(x)) G(x))– closed-loop control (predictor-corrector)16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Sensors!sonar rangefinderRobots’ link to the external world.Sensors, sensors, sensors!and tracking what is sensed: world modelsgyrocompassIR rangefinderodometryTsonar rangefinder16-735, Howie Choset with slides from G.D. Hager and Z. DoddsCMU cam with onboard processing
Tactile sensorson/off switchas a low-resolution encoder analog input: “Active antenna”Surface acoustic wavesCapacitive array sensorsResistive sensors16-735, Howie ChosetwithG.D. throughHager and Z. Dodds100% of light passes through90%ofslideslightfrompasses75% of light passes through
Tactile inci medical systemRobotic sensingMerritt systems, FL16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Infrared sensors“Noncontact bump sensor”(1) sensing is based on light intensity.“object-sensing” IRlooks for changesat this distancediffuse distance-sensing IR(2) sensing is basedon angle receved.IR emitter/detector pairIR detector16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Infrared calibrationThe response to white copy paper(a dull, reflective surface)raw values(put into 4 bits)inches15º incrementsin the darkfluorescent light16-735, Howie Choset with slides from G.D. Hager and Z. Doddsincandescent light
Infrared calibrationenergy vs. distance for various materials( the incident angle is 0º, or head-on )( with no ambient light )16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Sonar sensingsingle-transducer sonar timeline075µsa “chirp” is emittedinto the environmenttypically whenreverberationsfrom the initialchirp have stoppedthe transducer goes into“receiving” mode andawaits a signal.limiting range sensing.5safter a short time, thesignal will be too weakto be detectedtime responseblanking timePolaroid sonar emitter/receiversNolowerlimit16-735, Howie Choset with slides fromG.D.Hagerrangeand Z. Doddsfor paired sonars.
walls(obstacles)Sonar effectssonarDraw the rangereading that thesonar will returnin each caseT16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
walls(obstacles)Sonar effectssonarDraw the rangereading that thesonar will returnin each caseT16-735, Howie Choset with slides from G.D. Hager and Z. Doddsholding a spongeT
Sonar effects(a) Sonar providing anaccurate range measurement(b-c) Lateral resolution is not veryprecise; the closest object in thebeam’s cone provides the response(d) Specular reflectionscause walls to disappear(e) Open corners produce aweak spherical wavefront(f) Closed corners measure to thecorner itself because of multiplereflections -- sonar ray tracing16-735, Howie Choset with slides from G.D. Hager and Z. Doddsresolution: time / space
Sonar modelinginitial time responseaccumulatedresponsesblanking timecone widthresponse16-735, Howie Chosetspatialwith slidesfrom G.D. Hager and Z. Dodds
Sonar Modelingresponse model (Kuc) Models the response, hR,withc speed of sounda diameter of sonar elementt timez orthogonal distanceα angle of environment surfacesonar Sreadingαz oobstacle Then, allow uncertainty in themodel to obtain a probability:p( S o )chance that the sonar reading isS, given an obstacle at location o16-735, Howie Choset with slides from G.D. Hager and Z. Dodds
Roman Kuc’s animalsRodolphRobat16-735, Ho
16-735, Howie Choset with slides from G.D. Hager and Z. Dodds What’s Special About Bugs Many planning algorithms assume global knowledge Bug algorithms assume only local knowledge of the environment and a global goal Bug behaviors are simple: – 1) Follow a wall
168 Ariados Bug / Poison Chelicerata Arachnida Aranae Salticidae, jumping spider 213 Shuckle Bug / Rock n/a n/a n/a possibly an endolithic fungi 347 Anorith Rock / Bug n/a Dinocaridida Radiodonta Anomalocaris 348 Armaldo Rock / Bug n/a Dinocaridida Radiodonta Anomalocaris 451 Skorupi Poison / Bug Chelicerata Arachnida Scorpiones generalized .
reports using bug tracking software (such as Bugzilla), and then record which change in the SCM system fixes a specific bug in the change tracking system. The progression of a single bug is as follows. A programmer makes a change to a software system, either to add new functionality, restructure the code, or to repair an existing bug.
Filing a Bug Report - Existing Project File a Bug for an Existing Project - Title for bug! - Summarize - Be Descriptive - Select CSU or Component - Set Severity - Describe Module (file.c), Line of code or function - Attach supporting documents - Set Version ( tag from CMVC ) - Assigned to who? Sam Siewert 8 Be clear on bug .
Figure 2. Design of Space craft with robotic arm space in the launching vehicle compared to the traditional rigid, fixed geometry robotic arm. Figure 3. Morphing robotic arm section 3. DYNAMIC MODEL OF ROBOTIC ARM In this section, dynamic model of the morphing arm based on telescopic type morphing beam is derived. The robotic arm is assumed to .
4. Robotic Arm Writing Analysis using Neural Network Two-link robotic arm is designed in order to write any letter or word or many words in english language. Constraint workspace of motion the real two-link robotic arm is presented. in Figure 2. Robotic arm is writing using the parametric cartesian space trajectory planning analysis equations (7,
Abstract- In this paper we present the use of a 3R Lego robotic arm for teaching basic robotic concepts. The Lego Mindstorms NXT kit is an affordable equipment that can be used to better visualize robotic concepts usually taught in classes. The 3R Lego
What is Robotic Vision? This is where robotic vision differs from computer vision. For robotic vision, perception is only one part of a more complex, embodied, active, and goal-driven system. Robotic vision therefore has to take into account that its immediate outputs (object detection, segmentation, depth estimates, 3D reconstruction,
kidney (normal, mini or ultra-mini) we pass the telescope (nephroscope) through a sheath, along the track, to see the stone(s) inside the kidney (pictured). the stones are broken up using a laser, a lithoclast or an ultrasound probe and the larger fragments are removed using grasping forceps or suction when smaller nephroscopes (mini or ultra-mini) are used, the stones are .
