CS 326 A: Motion PlanningTypes of UncertaintyWhat is Uncertainty?PreimagePreimage BackchainingWhat is the Issue?ExampleSlide 8Computational ApproachCS 326 A: Motion CS 326 A: Motion PlanningPlanninghttp://robotics.stanford.edu/~latombe/cs326/2002Motion Planning with Motion Planning with UncertaintyUncertaintyTypes of UncertaintyTypes of UncertaintyIGWW11WW22• Uncertainty in model• Uncertainty in sensing• Uncertainty in controlWhat is Uncertainty?What is Uncertainty?Uncertainty = Distribution of possible errorsEnsemble distribution Optimize outcome in worst case(“game against nature”) Guaranteed strategy (2nd paper) EDR strategy (1st paper)Probabilistic distribution Optimize expected outcome Probabilistic strategyPreimagePreimageThe preimage of a goal G for a motion command (dir,term) is the largest subset P of C-space such that a motion starting from within P is guaranteed to end in G - dir is responsible for reaching G- term is responsible for recognizing that the goal has been attained dir = direction of motionterm = termination conditionPreimage BackchainingPreimage BackchainingProblem: goal G, initial region IRecursively compute preimages of G for multiple motion commands and preimages of these preimages, until a preimage contain I[Lozano-Pérez, Mason, and Taylor, 1983]What is the Issue?What is the Issue?Goal reachability and recognizability are interdependentThis means that a preimage depends on itself!!! (notion of fixed point)See paper by Lozano-Pérez, Mason, and TaylorExampleExampleBackprojectionfrom kernelKernel of goalExampleExampleComputational ApproachComputational ApproachSeparate reachability and recognizability, e.g.: kernel of goal + backprojection from kernel backprojection from landmark area in 2nd paper Incomplete planning or task
View Full Document