Interactive Navigation in Complex Environments Using Path Planning Salomon et al.(2003) University of North CarolinaContentBasic IdeaPrecomputation: SamplingSlide 5Guards & Connectors (C-space)Algorithm (build_roadmap)Search for a path: init goalDisplay Motion: Smooth PathUser-steered exploration (local walk)Local Walk AlgorithmDiscussionInteractive Navigation in Complex Environments Using Path PlanningSalomon et al.(2003) University of North CarolinaPrepared By Xiaoshan PanContent1st section (3/4)–Pre-compute a global roadmap–Graph search (inigoal) in real-time–Display motion2nd section (1/4)–User-steered explorationBasic IdeaPreprocessing phaseRuntime algorithmPrecomputation: SamplingGravity•Shooting raysRandom RaysPrecomputation: SamplingGravity•Shooting raysө ө•Walkable surface •Construct roadmap -Max # of samples-Min dist between samples•Connectors - Rc > RgRcGuards & Connectors (C-space)•Reachability (vs. visibility)Rg•Guards - guards can’t see each other- yes reject c, goto while c- no! c becomes a Guard, connect to connectors (if any), goto whileAlgorithm (build_roadmap)While (map_coverage < P_cover), do // map_coverage = guards_reachable/entire_spaceReturn roadmapConnectorGuardGuardConnectorGuardGuardConnectorGuardGuard2. Can c be a Connector? See any Guards in Rc? - Yes then connect, goto while (else goto 3) 1. Pick a random config. cc3. Can c be a Guard? See any Guards in Rg?cBe a Connector Be a Guard Be rejectedSearch for a path: init goalInitial position (Rc radius)inigoalGoal positionGraph search…Display Motion: Smooth PathWalk along the pathinigoalSmoothing path (cutting redundant corners while walking)User-steered exploration (local walk)User has control–A directional vectorRobot always stays on a walkable surface–In free space–Surface within a tolerance angle–Steps ok, cliffs NO!!Robot do not penetrate objectsLocal Walk AlgorithmFollow the directional vector, if- Goal is reached, stop- Collision, project along obstacle edge- New surface, step up/down (not a cliff!)- Edge, step up/down or project along the edgeDiscussionCan deal with complex environment–Because it pre-computes a global roadmap.Still…–Pre-computation could be time consuming.–Walking along line segments does not look natural.Overall assessment: Pretty good
View Full Document
Unlocking...