# 2D Robot # Chatterjee et al., Cost Analysis of Nondeterministic Programs # # **2D Robot** We consider a robot walking in a plane. Suppose # that the robot is initially located below the line y = x and # we want it to cross this line, i.e. the program continues until # the robot crosses the line. At each iteration, the robot prob- # abilistically chooses one of the following 9 directions and # moves in that direction: {0: North, 1: South, 2: East, 3: West, 4: # Northeast, 5: Southeast, 6: Northwest, 7: Southwest, 8: Stay}. # Moreover, the robotâ€™s step size is a uniformly random vari- # able between 1 and 3. At the end of each iteration, a cost is # incurred, which is dependent on the distance between the # robot and the line y = x. # Note: use approximation `tick(x-y)` instead of `tick(0.707 * (x-y))` def f(): var x, y, r, a, b x = a y = b while y <= x: prob(1,4): r = unif(1,3) y = y + r else: prob(1,7): r = unif(1,3) y = y - r else: prob(1,6): r = unif(1,3) x = x + r else: prob(1,5): r = unif(1,3) x = x - r else: prob(1,4): r = unif(1,3) x = x + r r = unif(1,3) y = y + r else: prob(1,3): r = unif(1,3) x = x + r r = unif(1,3) y = y - r else: prob(1,2): r = unif(1,3) x = x - r r = unif(1,3) y = y + r else: prob(1,1): r = unif(1,3) x = x - r r = unif(1,3) y = y - r # tick(0.707 * (x-y)) tick(x-y)