Berkeley ELENG C149 - Controller Synthesis (15 pages)

Previewing pages 1, 2, 3, 4, 5 of 15 page document View the full content.
View Full Document

Controller Synthesis



Previewing pages 1, 2, 3, 4, 5 of actual document.

View the full content.
View Full Document

Unformatted text preview:

Introduction to Embedded Systems Edward A Lee Sanjit A Seshia UC Berkeley EECS 149 Spring 2009 Copyright 2008 09 Edward A Lee Sanjit A Seshia All rights reserved Lecture 19 Controller Synthesis A Robot delivery service with moving obstacles start destination for robot At any time step Robot can move Left Right Up Down Stay Put Environment can move one obstacle Up or Down or Stay Put But only total of 2 times over all time steps Can model Robot and Env as FSMs Robot state its position Env state positions of obstacles and count EECS 149 UC Berkeley 2 1 Recap of topics covered last time start 1 Stated the goal in temporal logic F The problem is a reachability problem 2 Gave an algorithm to solve a version of the reachability problem 3 Considered some alternative goals F 1 F 2 F n F 1 F 2 F n EECS 149 UC Berkeley 3 Reachability Analysis Revisited The reachability problem Given an FSM M Q Q0 and a state is s reachable from some q0 Q0 by following System evolution according to is a sequence robot step env step robot step env step is reachable if there is some sequence of robot and env steps from q0 to This seq need not have the worst case env steps It s optimistic assumes helpful environment not adversarial EECS 149 UC Berkeley 4 2 Visualizing Optimistic Controller Synthesis S S S D Q0 Q1 Q2 Qk S obstacles stay put D obstacle moves down EECS 149 UC Berkeley 5 Synthesis with an Adversarial Environment Suppose at every step an adversary picks the worst possible action to stop the robot s progress This is a game between the system and its adversarial environment We want to modify the search performed by the reachability algorithm to handle this worst case behavior Any ideas EECS 149 UC Berkeley 6 3 Controllable States Idea Compute the set of states from which no matter what the environment does the robot can reach the red square Such states are called controllable states What are some examples of controllable states for our robot example EECS 149 UC Berkeley 7 Examples of



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Controller Synthesis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Controller Synthesis and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?