### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Special Topics CS 8803

GPA 3.81

### View Full Document

## 7

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 8803 at Georgia Institute of Technology - Main Campus taught by Michael Stilman in Fall. Since its upload, it has received 7 views. For similar materials see /class/234050/cs-8803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Special Topics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

M Sile RlMGl Lecture I Introduction Mike Stilman Robotics amp Intelligent Machines GT Georgia Institute of Technology 192009 The Golem Arti cial Being Uslally Follows Commands am was u 1om Century Rabbi of Prague Publ39shed in rst Golem made from d st 1847 Robot Karel caoek Czech wrimr 1921 Factory that makes ati cial people called Robots Wikipedia points out thatJosefCapek came up with the name other Historical msionaries Greek Mythology Hephaestus mechanical servants L eonardo da Vinci Humanoid Robot Knight Elektro Features Voice Command Walk ampTalk Smoke Cigarettes Blow up balloons Unimate PUMA Arms Victor Scheinman Up to 6 degrees of freedom 1937 Westinghouse Electric Corporation Seven feet tall humanoid 265 pounds 1956 First Commercial Robot George Devol Transport amp Welding for Auto Industry What makes humanoids different Anthropomorp hic Autonomous Multipurpose Futuristic Appea rance VS Function Nasa Robonaut Vecna BEAR UMass uBot H7 Univ Tokyo Digital Human Laboratory HRP2 Mike Digital Human Lab Armar Karlsruhe Monty Is Very Stable c 2007 Anybots Inc ALL RIGHTS RESERVED Fiction 0 possibly next year 0 eetures en leew te leuilei ieleea as necessary for progress 0 JekdseelesrhemewedeenelEess Fact 0 We Design and Build one Big Humanoid 0 Hands on learning 0 Teamwork and collaboration Schunk 7 DOF Light Weight Arm 20 kg Maximum Load 510 kg at reach ATI ForceTorque Sensor at Wrist CAN Interface to CurrentVelocityPosition Schunk Dexterous Hands 7 Degrees of Freedom Pressure sensors on ngers Not Yet Operational Plan Simulate robot dynamics Plan for basic functionality Estimate system requiremenis Design Build and Integrate obile base Robot torso Perception Systems Cameras Lasers Mechanical electrical and computational systerrs Develop and Implement Controls for balance Controls for arms and hands Visual and Haptic feedback systerrs Taking an active role in a major research project Hands on experience in applying software to robot development CAD Design SolidWorks AutoCAD Dynamic Simulation PhysX ODE GL Visualization Mathematics Matlab Mathematica Identifying and Purchasing Componenis based on specifications Building System Elemenis Machining smaller parts on CNC mi lathe Designing and assembling electronis Preparing larger parts for external manufacture Programming Controllers in CC on a Real Time operating system Systerrs Integration Putting all these skills together Tuesday Discuss what each group accomplished last week Resolve outstanding problems and challenges Plan activities for next week Thursday Each student presents and leads discussion on relevant research next slide As Necessary Instructor gives minitutorials on critical topics CAD Simulation MachiningElectronics Robot Controls Existing Humanoid Robot Designs Design and Control of Balancing Robots Walking Robots Control Strategies Motion Planning for Humanoid Robots 7 a Grasping Strategies Planning and Control Applying Learning Algorithms to Robot Control Force Control for Degtltterous Robots Vision ampSensing for Humanoid Robots Whole Body Motion Control We expect gt 1 class per topic but probably not more than two Applications of Humanoid Robots Lecture 19 Partially Observable MDP Mike Stilman Robotics amp Intelligent Machines GT Georgia Institute of Technology M Stilman RIMC1T 10292008 1 States 2 5177571 Actions A 01 am Rewards R r17 Warn Transition Model Pnext sl current 2 s and action a More general form of reward function Minor adjustment to previous definition Allows penalty for actions eg minimize torques Same actions in distinct states may have distinct rewards sleeping when you re full is better than when you re hungry States Rewards Transition Model Pnext sl current 2 s and action a What do we do if such a model does not exist Make one QLearning 1 Js Value of a state 1rs Optimal policy in the state Qas Value of taking an action in a state What do we do if such a model does not exist I Make one I QLearning Rule 1 Q alsi OLE r Y maxal Qt allsj 10 Q aSi o Uncertainty in the outcome ofactions o Uncertainty in sensors What is the system state L w an m wit 0 Terminology Localization State Btimation o Approaches POM DP Kalman Filter Particle Filter Originated in Operations Research General Optimization amp Management Science Drake 962 Astrom 1965 Smallwood 1973 Sondik 1978 Monahan 1982 Lovejoy 1991 Kan Johan Astrom Applied to Planning in 90s by Littman Kaelbling Cassandra Applied to Robots Koenig amp Simmons Andrew Ng V Ll M Littman L Kaelbling E 31 sn R 715123819 Transition Model States Actions A 01 Rewa rd 5 Ps la s Pnext s l current 2 s and action a States 2 1 Sn Actions A 01 am Rewards R 7quotai Transition Model Psas Pnext sl current 2 s and action a Observations Observation Function Probability of observation 0 in state s Generalization PO a 8 A belief state b is a probability distribution over MDP states Belief states have a transition model b s Psi0ab A belief state b is a probability distribution over MDP states Belief states have a transition model b s 7 Psl0ab Planning in terms of belief states is a high dimensional MDP where states are belief states POMDP is a continuous n dimensional state space Where n of MDP states Belief MDP State is a probability distribution over states of MDP M Belief MDP state State Transitions b 5 Ps l0ab Any MDP state PreVIous belief distribution Observation Action Belief MDP State is a probability distribution over states of MDP State Transitions Ps loab MDP Transition Function Observation Probability Previous Belief State Pols 51 Ps loc7 31b31 51P0l51252P51la752b52l Belief MDP State is a probability distribution over states of MDP State Transitions b 3 p3 lo7ayb Bayes Rule Pols abPs lab P0la7b Chain Rule Ps ab P0ab Ps labPab P0labPab I I PW b Pols gt251Plts imsnwsn P0lab 251 130l81lZs2 P81la7 82b82l I Belief MDP State is a probability distribution over states of MDP State Transitions 15 p5 l07 a7 1 Bayes Rule Chain Rule Pols 7 a bPs l0L7 b Pol0L7 b Pols 51 Ps loc7 31b31 51P0l51252P51la752b52l Belief MDP State is a probability distribution over states of MDP State Transitions My p3quot07a7 b Pols abPs lab Polab Pols 7 a b 51 Ps l0L7 b7 31P31l0L7 b Polab Total Probability Theorem Exercise Prove it P0ls ZS Ps la7 81b81 251 Polsll252 P31 a7 szbszl I Belief MDP State is a probability distribution over states of MDP State Transitions 15 Ps loab 7 Pols abPs lab 7 Polab P r P I P b Conditional O S zsl SW731 31 7 Independence Po a b P0l5 251 Ps la181P81lb Given 5 0 does not Pola b Depend on a b Likewise s does not Depend on b given 51 and a Belief MDP State is a probability distribution over states of MDP State Transitions 15 7 Ps loab Pols abPs lab Polab Pols ab Z351Ps loib7 31P31lab W W b Definition of b P0l8 251 P8 la7 81b81 ZSIPMSM P51la752b52 State Transition Probability in Original MDP Belief MDP State is a probability distribution over states of MDP State Transitions WSI Ps loab Pols 51 Ps l0L7 31b31 51P0l51lzszP5 la782b52l Expected Rewards of Original MDP States B bi Observations Q 017 Actions A 01 am 7071 Rewards PM 17 Z a S Transition Model b s Ps l0 a b P0l8 ZS P8la7 8W8 P0la b 39ust simpli ed notation Same as previous slide We will use a vector P1 P2 to represent a belief state bS1 P1 b82 P2 1 F 1 HH H H O Hara Rewards Ra b Z ra 55 RA17 3 2 x 71 gtlt 317 Rewards Ra b Z ra 55 s 351 RA17 31 2 x 71 x 3 17 51 9 X 3 X 76 X 3 P01A1b 305 Transmons 395 X 397 X I7I4 X 393 b s Ps oab b 52 W P0s ZS Ps a sbs Po ab Rewards Ra b Z ra 55 351 RA17 32 gtlt 71 x 3 17 bSl 7 9 X 3 X 76 X 3 P01A1b 305 Transmons 395 X 397 X I7I4 X 393 b s Psquot0ab W52 W 7 PMS ZS PS a7 SW5 P01A1b 351 305 656 7 PM W b Sl 351656 54 A2 RA2 73 1 7 31 Rewards Ra b Z ra 55 5 b s1 Ps102A173 1134 RA1 7 3 7 2 X 71 X 3 7 17 Transitions b s Psquot0ab P0s ZS Ps a7 sbs Po ab Rewards RA1 1311321 2P1 P2 2P1 17 P1 P1 1 RA2 P1P2D P1 3P2 7 P1 317 P1 7 3 7 m Rewards RA15 P1P2D RA25 P1P2D Transitions 7A1 31 POliSl 9 7A1S2 1 P01iS2 5 7A2 31 P02iSl 1 v 5 Rewards RA17P1P2 RA2P1P2 Transitions 7A1Sl2 1301131 g 7A1S2 7 1 1301132 5 7A2Sl 1 1302131 1 7A2 32 3 P02iS2 5 2P1P272P117P1P11 1D13P2P1317P1372P1 2P1P22P117P1P11 P13P2P1317P1372P1 51 P31iA 1 SlP1 PSl Ps1iA1 PP2 3131 6P2 3P1 6 P 8 9131 2P2 2 7P1 W31 Po PSliA1P1P2 3131 6P2 3131 5731 1 2P2 2 7P1 01m PlpzD OIiSIHSIiALiP 9 57 74 7 12131 Po2iA1 PleD 26 1211 Po1iA2 P1Pz 82 7 28F PO2iA2P1Pz 1828P1 PSliAl SlP1 P31iA1 S2P2 611 7 P1 iAlS2P2 1 7 P1 PS1i07a7b i81P81 P01iS Rewards W81 RA1P1P2 2P1P22P117P1P11 P0i81PS1ia7b RA2P1Pzi P13P2P1317P1372P1 P 011 b Transitions PSliA1 01 Png POliSlPSliAl P1P2P01 Al PJP2 7 1 2 9060 7 awn747121 PsuA2 P1Pz 87 7P1 54727P174 121 PS2iA2PPz 2 7P1 Ps2iA1o1 P1Pz 20 ram747 12131 Ps1iA2o1 P1P2 727 63P1827 28131 Ps2iA2o1 P1P2 1035P1827 28P1 PSliA102 PleD 06703P126 12131 P 02 A1 P1P 26 12p1 PS2iAL02VP1P2D 20 ISM25 12131 P01iA2PP2 827 28131 PSliA2VO2VP1P2D 08 07P DH 28131 P02iA2PP2 18 28p1 SZiA202PP2 1035P118 28131 Convert to MDP and then use Value Iteration How to use Value Iteration in a Continuous State Space Convert to MDP and then use Value Iteration How to use Value Iteration in a Continuous State Space RA2O 1 Wb 2 RA11 0 1 RA21 0 RA1o 1 V07 mgxlma b 7 2 PUI lMWUI H w o F39 1 1 RA1P1 le P11 RA2p le 37211 Property Value Function is Piecewise Linear amp Convex 3 Rome 11gt Vb maxRa b A Z Pb la bVb b Wb 2 RA11 0 RA1P1 le P11 1 RA2jl 0D RA27 P1 P2 3 2P1 RA1o 1 V1A1b RA1b7 0P11 0 F1 1 V1A2b RA2b7 03721 Values are Piece wise Linear amp Convex Lines or Hyperplanes Class 2 Scheduling and Teams Mike Stilman Robotics amp Intelligent Machines GT Georgia Institute of Technology M Stilman RIMC1T 192009 1 Sign up for 2 3 of the most interesting topics with initials Make a table of your initials and admin info on the back Existing Humanoid Robot Designs Asimo HRP2 Armar UMASS uBot etc A comprehensive review of existing humanoid robots What are the advantages disadvantages of different designs How are they relevant to our project Be Specific Modes of Locomotion Types of Actuators Types of Sensors System Architectures Capabilities amp Applications Best Places to Search 0 htt scholar oo lecom o httg1citeseeristgsuedu Use this tool to get GaTech Access to Papers httn39lwww lihran lanaih Incanzemhp You can look at digital archives directly by looking here 0 htt libra atechedu search databases h Example of a VERY useful digital archive i999 nm www lihran Harmh 139 n Go to the library Humanoids Lab Content Management System Central Information Resource Sections for each topic of design amp implementation Most Recent Information on Progress Relevant tools and links to resources Individual Blogs on Progress Your personal results and lessons learned Foundation of your grade for the course a eu quotth MM Mechanics what will the physical structure of the robot consist of Current set of part choices md manufacturers Links to ilppliers of parts and part manufacturers IConbact info for relevant nennie mire arison of componenls Actuation what actuators motors controllers inmrfaces does our robot need Sensors IWhat sensors could our robotuse Controls What controllers will we use IReferences on how to implement oontrolle rs Details on implementation and its relation to hardware on our project Blog Demonstrates the signi cant number of hours you re putting in to help your group and he project Helps you keep track ofwhat you ve done and the things you ve learned ou accom I E3 hieasz aaau u onsrwllh ex Ian onsplcturesgnd govl 51 w m Wu lExplana oviqnhomeylls mn be39d 02911 upli Challenges 51 Solutions what challenges did you face How id you overcome them Ilfnotovercome yet what options are you considering what are the other concepts you leaned about a 4 L lf nn ihl H help studenu Seminar Thursdays Topics for thursday discussions with abstr cts Provides links to papers for reading and slides 39om the seminar hEtTa F hm jilgsswons m quot as a amgJealquot559lvew a Abshact39containsgoalsifo presentaiion discuss on I 7 Papers 2 3 papers for each discussion Uploa d papers to CMS Easy access for39class at archiving IAdditional spaoe for forumrstyle discussion Order Parts 39 Implement Controls Initial Design amp Sim Implement Comp Elec amp Sensing lntegrate l1 l2 3 l4 5 l6 7 l8 9 l10 11 12l13 14l15l Complete Design amp Manufacture 5 Teams of 3 Students Responsibilities will change over time Grading is individual teams can change over time Space Welcome to the Humanoids Lab Central Watering Hole Additional Space for Robot Base ampTorso in RIM Center Meet with your groups anywhere Pick a group leader 7 In charge of oretrrbuthg the Workbad aho responswb e for achwevwng goa s Everyone Shou d Cmt bute 7 Use what you know Experiment to learn what you don39t Contact other grouDS to orecues how to make progess together and get the moat receht hto oh what thev ve eamed Write Up Results to the CMS mm 1 39 39 MS Surf Web Experiment for examp e r sav vou haven t used some software a Make a goa for you5ef to demon or make somethhg a Do the tutorwa a w to make rt fa m agah get he p Am s hn mu 1 Miami Lecture 21 Linear Control Mike Stilman Robotics ampIntelligent Machines GT Georgia Institute of Technology M Sniman RIMGD 1152005 1 Nick Maltin amp Neil What is a Dynamic System A system whose variables are timedependent Inputs and Outputs vary with time How can we describe a dynamic system Inputoutput differential equations Freebody diagran39s Statevariable matrix Transfer functions Block diagran39s State Variable Form i mm in State Variable Form mibdc f iaif 0 bio State Variable Form iiwwm State Variable Form 3 3 3 State Variable Form 2ng State Variable Form 039 0 1 a 0 939 5 1 939 2 9r 1 J J J 1kgm2 b 1Nms 9 5rad nnsmnn rad 6 a me 5 b 1 9T de erpwier b Kd KP KP 707 107 10 Jar J 39 b r b 1 a 70 a 7pr far 11 Kd KP KP J0 J0 JaJar a 5 me s Lecture 12 IK amp Robot Arm Planning Mike Stilman Robotics amp Intelligent Machines GT Georgia Institute of Technology M Stilman RIMGT 9262008 1 KUKA Industrial Arm KAWADA HRPZ UMAN U Mass Sony N30 0 Robot Con guration Spaoe Robot Joint Space 0 Robot Kinematics Mapping from joint angles to link positions where is this 0 Robot Con guration Spaoe Robot Joint Space H 0 Robot Kinematics Mapping from joint angles to link positions l where is this 0 Robot Con guration Spaoe Robot Joint Space 0 Robot Kinematics Mapping from joint angles to link positions where is this T3 TQTngT Robot Kinematics Mapping 1mm luim anglesln link Positions AKA Why do we need to know where the links are Because that39s all that really matters Where is my hand Where is my elbow Where is my oenter of mass Where are my eyes etc Because obstacles and constraints are in world ooordinats 0 Con guration State Space De ned by robotjoint values 0 Start State Current robotjoint values 0 Actions Displacements to robotjoints Are we done Con guration State Space De ned by robotjoint values Start State Current robotjoint values Actions Displacements to robotjoints Still to do GOAL SI39ATE Goals are rarely speci ed in joint ooordinates a I ac Ions How do we compute joint space obstacles o FonNard Kinematics Mapping from joint angles to link positions Inverse Kinematics Mapping from link positions to joint angles Goals are de ned in world ooordinates not joints coordinates Now given x3 and y3 solve for 91 and 92 1 C12 0 903 l1C1 12012 Last tune T3 512 0 13 l1S1 lzs12 Now given x3 and y3 solve for 01 and 92 Equations are nonlinear lots of Trig C12 512 I101 12012 x3 llcl 12012 0 7 Last tune T3 7 862 662 l15112512 gs 151 125 Multiple Solutions Not always possible to find closed form solution Infinite Solutions Very fast and numerically stable No general solution Each solution applies to a particular robot or class of robots Requires algebraicgeometric intuition Possible for robots with simple kinematics Robots with simple kinematics 6 DOF has closed form IK if either Three consecutive revolute axes intersect at a common point Three consecutive revolute axes are parallel to t Spherical WrIst rIS en er Wrist position not affected by 3 joints PUMA SMe 6 DOF Robot 305 p and R xg yg zg Goal PG and R PW PG d6zg Goal PG and RE X9 yg PW Do d6zg Forward kinematics for RN 0510 s O 7c O T391 0 1 0 0 Tim 0 O O l 515 of a 1 27 5152a TS TITQTS 5S Z J 51523 75152g 2g O 11251 S 53 11251 2 53 ES 0 mm 0 0 l O 0 0101202 agvzs 51a2c2 agczg mm agszg 1 1353 1353 Goal PG and R PW PG 616 52g 415 51 am agvza 51 751m in 51a252ag52g 52g 0 52 aasza Tg T31 ng 1 01 atan2PWy7PWx or 01 atanmpwwpwa Tr Goal PG and RE PW PG d6zy c g 415 51 01a252a3523 1202 agvza 2g 01 TOTOT1T2 515 751ng 751 51 a 1 2 a 523 52g 0 91 atau ywwpwz or 01 atau2ywwpvvz7r 12 a3 pr 13 1 7 2112113 00503 Goal PG and R2 PW PG 7 d6zg 51523 51523 51 T0T1T2 51023 75152g 1 2 a7 52 1202 Ham 701 51a2v2 13523 252 agszg 1 91 ata LVWyJVz 0r 91 atszWyaFvVz 7r pr 11 11 7 21213 00503 12 13 2 2 2 2 2 C PWx PWy pWZ 12 13 3 53 iql 6 p 2112113 W 03 atan2337 Cg Goat pa and RE x9 yg z PW Do d6zg 01023 70mg 51 0101202 agvza To T0T1T2 51023 75mg 701 51a202aavzg s 7 1 2 s 7 E 0 52g 2g 0 91 ata hvwwpwgc 0r 91 FILEDZWWyapvVz 7r 03 magma E 7P3V2P3VyP3Vz 7237a 3 2a ag 2 17 12 1303wZ 7 awn113w p vy 2 a2 1303 I Janay 1383pr C2 11 23 23 273 23 27 02 atan2527 62 Goal PG and RE Given R2 R3 RgTROG From Forward Kinematics C4C5C6 7 3436 7C4C536 7 34C6 C435 n 3 R2 s4C5C6 C436 734C536 C4C6 3435 mg 32 a 735C6 35 36 C5 nZ 32 a2 C4C5C6 7 3436 7C4C536 7 34C6 C435 n 3 R2 7 s4C5C6 C436 734C536 C4C6 3435 n1 3 735C5 3536 C5 nZ sz 05 E 07 7T atan ai7 a 646566 7 3436 7646536 7 3466 C435 n 3 R2 346566 C436 7346536 C466 3435 mg 32 a 73566 3536 nZ 32 12 95 E 07 77 atan ag7 1 Goat pa and RE x9 yg z 545556 3436 545536 3456 C435 n 3 1 R27 346566C436 734C536C466 3435 n1 3 a C5 nZ 32 az 056077T 04 atan2aa 3 05 atan2ai2ag27az Goal PG and RG x9 yg zg 949596 5456 949556 5496 54 9596 l 9456 549556 l 9496 i 596 5556 05 6 070 95 e 770 atan2aa atan27a 741 atan2 415392 413241 atan27 115332 413241 atan2s 772 atan275n o Dif cult to nd solution amp it does not always exist 0 Placs constraints on robot construction 0 The solution is very fast ALTERNATIVE 0 Differential Kinematiis 91 92 69 What is the robot Jacobian 673 6z 2 6zquot 69 69 69f Mannvan aw L9 6amp9 992 29 Matrix of Partial Derivatives of 2 5 669 666 669 Kinematics wrt each Joint variable 69 692 5 1 5 1 691 692 69 What is the robot Jacobian 6191 6 Menu7671 1 1 in 991 992 23 Matrix of Partial Derivatives of j Z 6 6 Kinematics wrt each omt variable 6 9z 6 9 if Why is it useful 5x 5x 561 E 661 E Workspace velocity Joint VeIOCity 5 1 291 292 3 What is the robot Jacobian 673 6z 2 6zquot 69 69 6h Mannvan aw Lu m g9 g9 69 Matrix of Partial Derivatives of 5 2 59 6m 6m 6w Kinematics wrt each 10int variable 69 692 Why is it useful 7 6t 7 661 626 Sac 661 9 612 512 Z10112012 3391 T3 512 C12 118112812 ll 2 0 0 1 61 Sac 590 561 562 451 12512 42512 1161 12612 12612 Algebraic Interpretation of Jacobian J01 Jan Z t t t JR 1 0 prlsmatlc Jomt Jo z x 005 1101 12012 130123 ye 1181 12812 138123 Xi y Z P z t t t t JR 0 prlsmatlcjomt 70 z X P P revolute joint Z 1151 12512 135123 1101 12012 130123 0 0quot 1101 12012 130123 J 0 X 1151 12512 135123 1 0 0 0 1 1151 12512 135123 1 1101 12012 130123 0 0 0 1 2512 135123 12012 130123 0 0 1 6 ye 0 0 1 1101 12012 130123 1131 12312 133123 1101 12012 130123 1101 X 115112512135123 1151 0 To Xi y Z P 0 0 0 1 J JPI Jpn 701 Jan Z JP 0 Jot Z X P 7p Z 1151 12512 135123 1101 12012 130123 J 0 0 1 prismatic joint revolute joint 42512 135123 12012 130123 0 0 1 131 M 435123 130123 0 0 0 1 005 1101 12012 130123 ye 1181 12812 138123 110112012 130123 1151 12512 135123 0 X1 1 Simulate a small displacement A t for each joint Observe A and place its value into J Less accurate more time oonsuming metimes the only option Workspaoe goal How do we get a joint spaoe goal Assuming 6 DOFancl J is full rank 0 Iterate until convergenoe Workspaoe goal How do we get a joint spaoe goal Assuming 6 DOFancl J is full rank Aq 17le o Iterate until convergenoe Otherwise Still Possible PseudoInverse ampVan39anls J JTJJT 1 0 Generally applicable to nDOF kinematics 0 Many existing implementations o Slower and unstable around singularities Yes goals for manipulators are really that complicated Imagine what it takes to represent obstacles l 4 939 r L39 r 7 7i But does this remind you of anything if Hint follow the gradient Oussama Khatib 86 Uaq Urq Uq Uaq J ancc Thanks to H Choset J Lee GHageramp ZDodds for icsl 22 Lecture 9 Motion Planning for Navigation Mike Stilman Robotics amp Intelligent Machines GT Georgia Institute of Technology M Stilman RIMC1T 9172008 1 local environment knowledge amp global goal Robot can tell the distance smell the goal Otherwise local sensing of walls B Q Reasonable World Finite obstacles in finite space Workspace is bounded Mi 51mm Completeness is Desirable Optimality is Desirable Early Motion Planning Algorithm Nodes share an edge if they are within line of sight A points in free space are within sight of at least one node Completeness does not always require complexity Bug Algorithms achieve global completeness with local planning Bug Algorithms are not Optimal Visibility Graphs are Optimal I Completeness What are the assumptions Bug Algorithms Finite Obstacles in Finite Space Visibility Graph Completeness What are the assumptions Bug Algorithms Finite Obstacles in Finite Space Visibility Graph Polygonal Obstacles I Completeness What are the assumptions Bug Algorithms Finite Obstacles in Finite Space Visibility Graph Polygonal Obstacles Optimality What is the metric Visibility Graph Euclidian Distance Traveled Provable The optimal path in this graph is the shortest plan Finding an optimal solution Uniform Cost Search A Search Mi limm 1976 Tomas Lozano Perez MS Thesis LAMA The design of a mechanical Assembly System The assembly problem is seen as the problem of achieving a certain set of geometrical constraints between basic objects while avoiding unwanted collisions 1979 Tomas Lozano Perez Visibility Graphs 1980 Tomas Lozano Perez Spatial Planning A Con guration Space Approach Most common interpretation of path planning A configuration is a set of parameters that de ne the robot geometry in the world How many parameters TWO XY A configuration is a set of parameters that de ne the robot geometry in the world Plan in Parameter Space Space Dimension 2 Configuration Space Transform Minkowski Sum A configuration is a set of parameters that de ne the robot geometry in the world Plan in Parameter Space Space Dimension 2 Configuration Space Transform Configuration Space Transform with Rotation 2 Con guration Space Transform with Rotation 3D Con guration Space E One Slice where 9 is fixed A39 4 m0 mnm Set of vertices v1 vn For each vertex vi For each vertex vj test whether edge vivj is collision free Set of vertices v1 vn For each vertex v For each vertex vj test whether edge vivj is collision free Collision test for each edge echeck if vi Vj intersects e On Test Edges On Obstacle Edges OnZ Tests Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle I Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions V5 Update Edge List Remove nished edges Add started edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions Update Edge List 0 Remove nished edges 0 Add started edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions V5 Update Edge List 0 Remove nished edgesH 0 Add started edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions Update Edge List 0 Remove nished edges 0 Add started edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions V5 Update Edge List 0 Remove nished edges 0 Add started edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions Update Edge List v6 0 Remove nished edges 4 V3 0 Add started edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle 2 Test visibility in order of angle Keep a list of active edges Test only active collisions V5 Update Edge List 0 Remove nished edges 0 Add started edges Method 2 Plane Sweep For each vertex vi 1 Sort vertices by angle On On log n 2 Test visibility in order of angle Keep a list of active edges Test only active collisions V5 Update Edge List v6 0 Remove nished edges V4 0 Add started edges Necessary edges Edge between Reflex Vertices Reflex Inner Angle gt 7r Necessary edges Edge between Reflex Vertices Reflex Inner Angle gt 7r Bitangent Lines Connects two Reflex Vertices Does not poke into interior Add the start and goal to the graph Search Cost Distance along edge 0lEl M Visibility Graphs are complete Yes Assuming Polygonal Obstacles Visibility Graphs are optimal Yes Metric Distance Traveled Drawbacks Polygonal Environments W1 imam q Drawbacks Polygonal Environments Zero Distance to Obstacles Lets color this space How would you distribute the continuous space into 4 colors Space Coloring Associate each point with the area closest to it Boundaries have maximum distance to points Gregory Voronoi 18681908 student of Andrey Markov sound familiar Extending to polygonal objects 0 Features ofan obstacle are vertices and edges 0 A roadan edge must be between some pair of features 0 edge edge vertex vertex vertex edge Extending to polygonal objects 0 Features ofan obstacle are vertices and edges 0 A roadan edge must be between some pair of features 0 0n Algorithm Computes amp Intersects these curves o On log n edge 7 edge vertexr vertex vertex 7 edge Online Diagram Generation Locate two nearest features and move to midpoint Online Diagram Generation Locate two nearest obstacles and move to midpoint Continue along GVG edge until meet point 21 Online Diagram Generation Locate two nearest obstacles and move to midpoint Continue along GVG edge until meet point Detect new GVG edges Select one to explore and continue Online Diagram Generation Locate two nearest obstacles and move to midpoint Continue along GVG edge until meet point Detect new GVG edges Select one to explore and continue Detect boundary points and cycles 22 Brushfire GVG Generation 0 Start with an empty grid with obstacles 1 23 Brushfire GVG Generation Wavefront Start with an empty grid with obstacles 1 Expand all cells i to i1 If a cell is expanded twice label as a GVG edge and do not egtltpand further Brushfire GVG Generation Wavefront Start with an empty grid with obstacles 1 Expand all cells i to i1 If a cell is expanded twice label as a GVG edge and do not egtltpand further 24

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.