Kinodynamic Path PlanningWhere PRMs Fall ShortPath Planning in the Real WorldOutlineSlide 5Two Approaches to Path PlanningRepresenting Static StateRepresenting Dynamic StateSlide 9Incorporating Dynamic ConstraintsRegions in State SpaceConstraints on ManeuveringSlide 13Slide 14Planning Amidst Moving ObstaclesProblemAsteroid Avoidance ProblemMOP OverviewSlide 19Building the RoadmapBuilding the Roadmap (cont.)Solution TrajectoryMOP details: Inputs and OutputsMOP details: Roadmap ConstructionSlide 25MOP details: Uniform DistributionAchieving Uniform Node DistributionSlide 28Slide 29Slide 30Demonstration of MOPSlide 32SummarySlide 34Planning with RRTsHow it WorksBuilding an RRTSlide 38Executing the PathPrinciple AdvantageAdvanced RRT AlgorithmsExample: Simple RRT PlannerGoal-biased RRTSlide 44The world is full of…Bidirectional PlannersBidirectional Planner AlgorithmBidirectional Planner ExampleSlide 49DemosConclusionsSlide 52Kinodynamic Path PlanningAisha Walcott, Nathan Ickes,Stanislav FuniakOctober 31, 2001Where PRMs Fall ShortUsing PRM1. Construct roadmap2. A* finds path in roadmap3. Must derive control inputs from pathPath itself is not enough: need control inputsCannot always execute an arbitrary pathPath Planning in the Real WorldReal World RobotsHave inertiaHave limited controlabilityHave limited sensorsFace a dynamic environmentFace an unreliable environmentStatic planners (ex. PRM) are not sufficientHave limited sensorsFace an unreliable environmentStatic planners (ex. PRM) are not sufficientOutlineExploring the problemPlanning amidst moving obstaclesRRT-based plannersDemonstrationConclusionsOutlineExploring the problemPlanning amidst moving obstaclesRRT-based plannersDemonstrationConclusionsTwo Approaches to Path PlanningKinematic: only concerns the motion, without regard to the forces that cause it Performs well for systems where position can be controlled directlyDoes not work well for systems with significant inertiaKinodynamic: incorporates dynamic constraintsPlans velocity as well as positionRepresenting Static StateConfiguration space represents the position and orientation of a robotSufficient for static planners like PRMExample: Steerable carConfiguration space (x, y, )xyRepresenting Dynamic StateState space incorporates the dynamic state of a robotxyExample: Steerable carState spaceX = (x, y, , x, y, )...Representing Dynamic StateWorking in state space allows planner to incorporate dynamic constraints on pathExamples: maximum velocity,Examples: minimum turning radiusWorking in state space doubles the dimensionality of the planning problemMath becomes exponentially harderIncorporating Dynamic ConstraintsRobot actuators can apply limited forceFor some states, collision is unavoidablePath planner should avoid these statesObstacleImminent collision regionCollision regions: XcollClearly illegalRegion of Imminent Collision: XricWhere robot’s actuators cannot prevent a collisionFree Space: Xfree = X – (Xcoll + Xric)Collision-free planning involves finding paths that lie entirely in XfreeRegions in State SpaceXcollXricXfreeNot all degrees of freedom are controllableConsider a steerable carEquation of Motion: G( s, s ) = 0Constraint is a function of state and time derivative of stateConstraints on ManeuveringSystem has 3 dof (x, y, ), but only one controllable dof (steering angle)..Constraints on ManeuveringNonholonomic: fewer controllable DOFs than total DOFsNonholonomic systems cannot execute an arbitrary path in configuration spaceThis is a problem for PRM and other configuration space plannersOutlineExploring the problemPlanning amidst moving obstaclesRRT-based plannersDemonstrationConclusionsPlanning Amidst Moving ObstaclesPlanning Amidst Moving ObstaclesMoving Obstacles Planner (MOP):A PRM extension that accounts for both kinematic and dynamic constraints of a robot navigating amidst moving obstaclesProblemKinodynamic motion planning amidst moving obstacles with known trajectoriesExample: Asteroid avoidance problemAsteroid Avoidance Problemhttp://antwrp.gsfc.nasa.gov/apod/astropix.htmlAutonomous Vehicle“Spacecraft”Moving Obstacles“Asteroids”Known trajectoriesDocking stationPath-planning among moving obstacles with known trajectoriesMOP OverviewSimilar to PRM, exceptDoes not pre-compute the roadmapIncrementally constructs the roadmap by extending it from existing nodesRoadmap is a directed tree rooted at initial state time point and oriented along time axisMOP OverviewFor each query, the planner incrementally builds new roadmap in state time spaceWhy? The environment includes moving moving obstaclesobstacles that change location (state) continuously with timeEach node in the roadmap must be indexed by both its state and the time it is attainedEx: node n is valid at time t, however at time t+ node n collides with a moving obstacleBuilding the RoadmapNodes(state, time)Collision- free? Randomly choose existing node1. Randomly choose an existing node Select control input u at random2. Randomly select control input u3. Randomly select integration time interval [0, max ]Integrate equations of motion from an existing node with respect to u for some time interval 4. Integrate equations of motionBuilding the Roadmap (cont.)Collision-free trajectory5. If edge is collision-free thenStore control input u with new edgeu6. Store control input with new edgeAdd new node7. Add new node to roadmapResult: Any trajectory along tree satisfies motion constraints and is collision-free!Nodes(state, time)Solution TrajectoryStart state and time (sstart, tstart)Goal state and time (sgoal, tgoal)1. If goal is reached then2. Proceed backwards from the goal to the startMOP details: Inputs and OutputsPlanning Query:Let (sstart , tstart ) denote the robot’s start point in the state time space, and (sgoal , tgoal ) denote the goal tgoal Igoal , where Igoal is some time interval in which the goal should be reachedSolution Trajectory:Finite sequence of fixed control inputs applied over a specified duration of timeAvoids moving obstacles by indexing each state with the time when it is attainedObeys the dynamic constraintsMOP details: Roadmap ConstructionObjective: obtain new node (s’, t’)s’ = the new state in the
View Full Document
Unlocking...