CS 326 A: Motion PlanningExploration Map BuildingExampleSlide 4Localization IssueCorrespondence ProblemSlide 7Loop IssueNot a New Issue!Two Sub-problems in ExplorationOther Exploration IssuesSlide 12CS 326 A: Motion CS 326 A: Motion PlanningPlanninghttp://robotics.stanford.edu/~latombe/cs326/2002Planning Exploration Planning Exploration StrategiesStrategiesExploration Exploration Map Building Map BuildingA robot is introduced in a new environmentIts task is to build a model (2D or 3D) of this environmentIt goes from place to place.At each place it acquires a local model that it merges with the current global modelExampleExampleExampleExampleLocalization IssueLocalization IssueInitial position of the robot reference coordinate frameDead-reckoning (e.g., odometry) yields increasing errors Need to match each new local model with current global model (correspondence problem)Correspondence ProblemCorrespondence ProblemLocalization IssueLocalization IssueInitial position of the robot reference coordinate frameDead-reckoning (e.g., odometry) yields increasing errors Need to match each new local model with current global model Simultaneous Localization and Simultaneous Localization and Mapping (SLAM)Mapping (SLAM)Loop IssueLoop IssueCourtesy R. ChatilaLoops Complex optimization problem(incrementality vs. global optomization)Not a New Issue!Not a New Issue!Two Sub-problems in Two Sub-problems in ExplorationExplorationWhere to go next?Where to go next?- Maximize amount of new information- Maximize amount of new information- Ensure minimal model overlap- Ensure minimal model overlap- Minimize travel length- Minimize travel length Next-best viewNext-best viewHow to best merge the two models?How to best merge the two models?- Minimize expected errors: Kalman filtering, - Minimize expected errors: Kalman filtering, expectation maximization (most likely map)expectation maximization (most likely map)Other Exploration IssuesOther Exploration IssuesMap model: polygonal, occupancy Map model: polygonal, occupancy grid, topological network, 3D surfaces, grid, topological network, 3D surfaces, object map, etc…object map, etc…Moving objectsMoving objects““Meaning” of objectsMeaning” of objectsMultiple robotsMultiple robotsUnstructured environmentsUnstructured environmentsOther Exploration IssuesOther Exploration IssuesMap model: polygonal, occupancy Map model: polygonal, occupancy grid, topological network, 3D surfaces, grid, topological network, 3D surfaces, object map, etc…object map, etc…Moving objectsMoving objects““Meaning” of objectsMeaning” of objectsMultiple robotsMultiple robotsUnstructured environmentsUnstructured
View Full Document