COMP155Computer SimulationSeptember 3, 2008Example: States and EventsExample: States and EventsEvent Driven TransitionsEvent Driven TransitionsStates and Events A state is a condition of a system at some point in time An event is something that cause a system to shift from one state to anothershift from one state to anotherFinite State Automata (FSA) a set of states one designated start state input alphabetthese are eventsthese are events a transition function that maps input symbols and current states to a next stateFSA Example: A Light SwitchtoggleONOFFtoggleFSA Example: A Light Switch states = { ON, OFF } start state = OFF alphabet = { toggle }transition function:transition function:current state ON OFFtoggle OFF ONFSA: GhostROAMsee=falsesee=falsesee=falseCHASE EVADEblue=truesee=truesee=trueblue=trueblue=truesee=trueFSA Example: Ghost states = { ROAM, CHASE, EVADE } start state = ROAM alphabet = { see=true, see=false, blue=true }transition function:transition function:current state ROAM CHASE EVADEsee=true CHASE CHASE CHASEsee=false ROAM ROAM ROAMblue=true EVADE EVADE EVADETraffic Lights: Systemsensorsinputs:4 sensors clock (every 5 seconds)lightsoutput:4 lights: red, yellow, greenTraffic Lights: Analysis East-West lights are the same North-South lights are the same Clock is used to introduce delayslights do not immediately switch when a vehicle is lights do not immediately switch when a vehicle is sensed caution (yellow) for 10 seconds before stop (red)Traffic Lights: States State is made up of three values: NS: color of north and south lights EW: color of east and west lightsD: integer used to distinguish between delay statesD: integer used to distinguish between delay statesNS: GEW: RD: 0Traffic Lights: Inputs Input Alphabet: SNS: north-bound or south-bound sensor triggered SEW: east-bound or west-bound sensor triggeredC: clock elapsedC: clock elapsedTraffic Lights: FSANS: GEW: RD: 1NS: YEW: RD: 2NS: YEW: RD: 1C CCSEWNS: GEW: RD: 0NS: REW: GD: 0NS: REW: GD: 1NS: REW: YD: 2NS: REW: YD: 1CCC SNSTraffic Lights: Tabular FSAGR0 GR1 YR2 YR1 RG0 RG1 RY2 RY1C GR0 YR2 YR1 RG0 RG0 RY2 RY1 GR0SNSGR0 GR1 YR2 YR1 RG1 RG1 RY2 RY1SEWGR1 GR1 YR2 YR1 RG0 RG1 RY2 RY1Once the FSA is in tabular form, implementation is straightforward:• hardcode: nested switch statements• flexible: read FSA from a table data structureTraffic Lights: Tabular FSAGR00GR11YR22YR13RG04RG15RY26RY171 = C 0 2 3 4 4 6 7 02 = SNS0 1 2 3 5 5 6 73 = SEW1 1 2 3 4 5 6 7States and inputs mapped to integer codes,to enable table lookupImplementation: Pythonclass TrafficLights:def __init__(self):self.state = 0self.transitions = ((0,2,3,4,4,6,7,0), (0,1,2,3,5,5,6,7), (1,1,2,3,4,5,6,7))self.NS_output = ('green', 'green', 'yellow', 'yellow', 'red', 'red', 'red', 'red')self.EW_output = ('red', 'red', 'red', 'red', 'green', 'green', 'yellow', 'yellow')def update(self, input):if (input < 1) or (input > 3): returnself.state = self.transitions[input-1][self.state]def display(self):printprint 'NS lights: ' + self.NS_output[self.state]print 'EW lights: ' + self.EW_output[self.state]printImplementation: Pythonlights = TrafficLights()while True:lights.display()input = int(raw_input("next input: "))if input == 0: breakif input == 0: breaklights.update(input)Exercise Design a FSA for a soda vending machineProbabilistic TransitionsProbabilistic TransitionsNondeterministic Automata A nondeterministic automata has probabilistic transitions called Markov modelsImplemented using time-steppingImplemented using time-stepping at each clock, probabilities are used to determine next stateMarkov Example: Diabetes Patients Three states: CD: controlled diabetes ESRD: end-stage renal disease D: deathTransitions:Transitions: Each year, patients with controlled diabetes have an 85% chance of staying in that state, a 10% chance of moving to the ESRD state, and a 5% chance of dying.  Each year, patients with ESRD have a 70% chance of continuing in the ESRD state and a 30% chance of dying.  Patients who have died have a 100% chance of staying dead.Markov Example: Diabetes Patients Time step: 1 yearESRD0.10.850.7CDESRD0.1D0.050.31.0probabilities out of any state must sum to 1.0Markov Model Implementation Generate a random number (0.0, 1.0) Use random number and current state to generate next stateif state is CD:if state is CD:if rand < 0.1: state  ESRDelse if rand < 0.1+0.05: state  D else state  CDelse if state is ESRD:if rand < 0.3: state  Delse state  ESRDelse:state  Dnote: need to add up previous probabilitiesImplementation: C++class DiabeticPatient{public:enum State { CD, ESRD, D };// constructor: set initial state and transition probabilitiesDiabeticPatient(); DiabeticPatient(); // Transition function: changes statevoid update();// output functions: simply return current stateState output() { return state; }private:State state; // current statedouble transition_probability[3][3]; // transition table};Implementation: C++// constructor: set initial state and transition probabilitiesDiabeticPatient::DiabeticPatient() : state(CD) {transition_probability[CD][CD] = 0.85;transition_probability[CD][ESRD] = 0.10;transition_probability[CD][DEAD] = 0.05;transition_probability[ESRD][CD] = 0.00;transition_probability[ESRD][CD] = 0.00;transition_probability[ESRD][ESRD] = 0.70;transition_probability[ESRD][DEAD] = 0.30;transition_probability[DEAD][CD] = 0.00;transition_probability[DEAD][ESRD] = 0.00;transition_probability[DEAD][DEAD] = 1.00;}Implementation: C++// Transition function: change state based on current// state and probability parameters.// Each update represents one year.void DiabeticPatient::update(){float r = double(rand())/RAND_MAX;float r = double(rand())/RAND_MAX;if (r < transition_probability[state][CD]) state = CD;else if (r < transition_probability[state][CD]+transition_probability[state][ESRD]) state = ESRD;else state = D;}Utilizing the Simulation How would you use this simulationto answer the following questions?  Suppose we begin with 10,000 patients with controlled diabetes. In 10 years, how many patients will still have controlled diabetes? How many will have ESRD? How many will have died? In 20 years, how many patients will be in each state?  How many years will it take before all of the patients are