Means-ends analysisReviewSlide 3Error feedback controlBehavior-based control (“Bottom-up”)Plan-based control (“Top-down”)Planning-based control (“Top-down”)Logic-based representations of the state spaceSlide 9GPS (Newell and Simon)The STRIPS representationPlanning with STRIPSReactive planning in fully reactive systemsGRL exampleComputing activation-levelsCompile-time property listsMaking the behaviorComputing desirable?Computing runnable?Gatherer functionsComputing conflicted?Slide 22Slide 23Slide 24A pathetic exampleSlide 26Compiled codeMeans-ends analysisNorthwestern UniversityCS 395 Behavior-Based RoboticsIan HorswillReviewRobot operates in an environmentState space SSet of possible motor outputs ADynamics (physics) that determines how the environment changes stateContinuous dynamics (continuous-time actions)f = dS/dt: SA  S,f = d2S/dt2: SA  S, etc.Discrete dynamics (atomic/ballistic actions, discrete time): SA  SReviewWant to construct a policy to make the robot do the right thingp: S  AComplete environment-robot system evolvesContinuous case: curve through state-spaceds/dt = f(s,p(s))Discrete case: system evolves through series of statess0s1 = (s0, p(s0))s2 = (s1, p(s1)) = ((s0, p(s0)), p((s0, p(s0))))Etc.Error feedback controlGoal state sgControl action computed from errords/dt = f(s- sg)d2s/dt2 = f(s- sg)Linear feedback controlf is a linear operatords/dt = k(s- sg)P control (proportional control)k is a gain you multiply byk is a matrix when s is a vectord2s/dt2 = kp(s- sg)+ kd ds/dt + ki ∫s dtPID controlBehavior-based control(“Bottom-up”)Combine policies by running them in parallelBehavior = policy + triggerBottom-up integration of behaviorsMap several behaviors to a single composite behavior (or composite policy)Several different composition operatorsBehavior-or (prioritization/subsumption)Behavior-+ (motor schemas/potential fields)Behavior-maxWeighted votingEtc.Plan-based control(“Top-down”)Combine policies by running them seriallyBehaviors → atomic actionsStill policy + activation levelExternally triggeredSelf-terminatingCombine behaviors using serial controllers (plans)Finite state machinesIndividual states canTrigger actionsWait for them to terminateWait for other external conditionsEtc.Planning-based control(“Top-down”)Combine policies “non-deterministically”Idea: “guess the action that will ultimately work”i.e. guess the one that leads to the goalProblem: this doesn’t help muchDon’t know which action(s) will ultimately workIf you guess wrong, you’re screwedSolution: simulationRun actions in simulationSearch through possible sequences of actions (plans) to find one that works and remember itExecute the successful plan in the real worldLogic-based representations of the state spaceRepresent states using propositions(true/false statements)Find a set of propositions that let you distinguish all the states you care aboutState = truth of each propositionAdvantage: partial state descriptionsP^Q is the set of states in which both P and Q are trueMeans-ends analysisPair goals up with actionsFor each proposition, keep track of the actions that can make it trueFor each action, write the precondition (partial state descriptions) for being able to run itTo solve the goal P^QLook up the action A that achieves PRecursively solve precondition(A)Run ARecursively solve Q without “clobbering” PGPS (Newell and Simon)“General Problem Solver”Used means-ends analysisAssumed priority ordering on propositionsAlgorithm:GPS(goal)while goal not yet true p = highest priority unsatisfied subgoal (subgoal = proposition inside of goal) a = action to solve p GPS(precondition(a)) do aThe STRIPS representationDefine actions in terms ofAdd list: propositions the action makes trueDelete list: propositions the action may make falsePrecondition list: propositions that must be true in order to run the actionPlanning with STRIPSGoal = set of propositions to make trueAlgorithm:STRIPS(initial, goal)for each subgoal p in goal not in initial for each action a with p in its add list try the plan: STRIPS(initial, precondition(a)) a STRIPS(initial-delete_list(a) +add_list(a), goal) if both recursive calls worked, we win else, try another action, or another subgoalReactive planning in fully reactive systemsCollection of behaviorsEach behavior achieves some goal(s)Each behavior has some precondition(s)Higher level system drives some goal signalGoal signalsActivate behaviors that achieve themDrive goal signals of preconditionsExamples:GAPPS (Kaelbling 90), Behavior Networks (Maes 90)GRL exampleExtended STRIPS representationOperators are just behaviors that activate themselves when they can achieve a goal.(define-operator name motor-vector (achieves add-list-signals …) (clobbers delete-list-signals …) (preconditions precondition-signals ...) (serial-preconditions precondition-signals ...) (required-resources names ...) (priority number))Computing activation-levelsA behavior is runn able if all its preconditions are satisfiedIt is desirable ifIt satisfies a maintenance goalIt satisfies some unsatisfied goal of achievementIt is unconf licted ifIt doesn’t clobber a satisfied goal or a maintenance goal, andNone of its resources are required by desirable operators of higher priorityCompile-time property lists(define-signal-property (add-list x) '())(define-signal-property (delete-list x) '())(define-signal-property (preconditions x) '())(define-signal-property (serial-preconditions x) '())(define-signal-property (priority x) 0)(define-signal-property (required-resources x) '())Making the behavior(letrec ((the-behavior (behavior (run? the-behavior) motor-vector-signal))) the-behavior)(define-signal (run? x) (and (desirable? x) (runnable? x) (not (conflicted? x))))Computing desirable?(define-signal-modality (desirable? x) (define adds (add-list x)) (signal-expression (or (apply or (unsatisfied-goal adds)) (apply or (maintain-goal adds))) (drives (goal (runnable? x))) (operator x)))Computing runnable?(define-signal-modality (runnable? x) (signal-expression