ibm talk3

Frobocup a DSL for Robotic Soccer: 

Frobocup a DSL for Robotic Soccer Functional Programming as a DSL construction kit -- featuring -- Haskell and Functional Reactive Programming (FRP) John Peterson, Andrei Serjantov, Paul Hudak Yale University

Robocup: The Video: 

Robocup: The Video Robocup is an international robotic soccer competition A test of both hardware and software skills!!

The Domain: Robocup: 

The Domain: Robocup Central Computer Camera Robots Ball All robots controlled by one computer Overhead camera tracks robots and ball Radio link

Robocup Challenges: 

Robocup Challenges Hardware design and construction Control system design Sensing (vision) Strategy  Our emphasis Uncertainty (the opponents) Why is the strategy hard? An effective system must integrate control systems, switching logic, planning, reasoning, assessment, and learning. Users need to rapidly explore the design space, building, testing, and assessing strategies. Our approach: a Robocup Domain Specific Language

About DSLs: 

About DSLs A DSL combines a vocabulary (primitive types and functions) with the ability to capture patterns (abstractions) We use an embedded DSL: implemented within an existing language. Haskell + vocabulary = DSL Haskell contributes composability (explicit interaction among components, laziness) and polymorphic typing (safety) Use Functional Reactive Programming (FRP) to manage interaction in a purely functional way Based on earlier work on robotics (Frob), vision (FVision), and animation (Fran)

The Key: Composibility: 

The Key: Composibility Objectives: To express simple control systems in a natural and declarative manner (following a ball) To alter robot behavior depending on context (obstacle avoidance) To commit to and execute complex parameterized behaviors (control systems) based on situation (planning, learning) To assign tasks to robots (control a group in unison, allocate specialized tasks) To express coordinated motion of several robots

Implementation Architecture: 

Implementation Architecture Frobocup Haskell Java

FRP and Behaviors: 

FRP and Behaviors Functional Reactive Programming is a functional model of interaction with the outside world Basic data type (polymorphic!!) Behavior a -- value of type `a’ that evolves in time r :: Robot botPosition r :: Behavior Point2 botOrientation r :: Behavior Angle botVelocity r :: Behavior Vector2 robotSize r :: Float Time varying aspects of the robot Static (non-varying) aspect of the robot Underlying static type Type that models a robot on the field

Using Behaviors: 

Using Behaviors type Behavior a = Time -> a  idealized Operators may be lifted into the behavioral domain: lift2 :: (a -> b -> c) -> (Behavior a -> Behavior b -> Behavior c) lift2 f = \x y t -> f (x t) (y t) FRP defines many lifted operators, including arithmetic (+, -, *, /) and comparisons (>, <, ==). Also integral, derivative. A lifted conditional: ifB :: Behavior bool -> Behavior a -> Behavior a -> Behavior a ifB = lift3 (\b x y -> if b then x else y) Behaviors hide the flow of time: no need for iterative control loops.

Types: 

Types data World = a set of behaviors defining robots, ball position data Controls = a set of behaviors controlling all the team’s robots (motor voltages) data Robot = behaviors defining a robot’s position and orientation data RControl = motor voltages for a single robot at a single time step type SystemController = World -> Controls

Example: Goalkeeper: 

Example: Goalkeeper keeper: World -> Robot -> RControlB keeper w bot = let v1 = ball w .-. rPlace bot v2 = ball w .-. goalCenter vec = normV v1 – normV v2 (s,d) = vector2PolarCoord vec in (s,d) Ball bot Goal v2 v1 This control system is valid only if: Robot is near the goal Robot is relatively far away from v1 (s is not too small) This validity region can be expressed using the boolean behavior: (s >= 0.1) && (near_goal bot) vec v2

Validity Regions: 

Validity Regions If you are too far from the goal, run back as fast as possible If you are lined up between the goal and the ball, kick it away Validity region Validity region Behavior Behavior

Composing Control Systems using Validity Regions: 

Composing Control Systems using Validity Regions Capture this structure in an abstraction: type Controller a = (Behavior Bool, a) Region Control blocker :: Controller RControlB blocker = ((s >= 0.1) && (near_goal bot), keeper w bot) Use this abstraction to create composite controllers (.+.) :: Controller a -> Controller a -> Controller a (b1,c1) .+. (b2,c2) = (b1 || b2, (ifB b1 c1 c2)) Favors first controller when both are valid

Example: a Better Goalkeeper: 

Example: a Better Goalkeeper gkeeper :: World -> Robot -> RControlB gkeeper w bot = ((s <= 0.1) && (near_goal bot),go_for_ball w bot) .+. (not (near_goal bot), runBack w bot)) .+. ((s >= 0.1), keeper w bot)

Variations on Combination: 

Variations on Combination The .+. combinator uses supression – we can also join valid controllers in other ways. Vector field control allows controllers to be joined via vector addition type VController = Controller Vector2 (.++.) :: VController -> VConroller -> VController (b1,c1) .++. (b2,c2) = (b1 || b2, (ifB b1 (ifB b2 (c1+c2) c1) c2)) The point of this: it is easy to define these patterns in a way that supports Compositional programming: building complex controllers from simpler ones in a transformational style

Reactivity: 

holdPosition `until` ballKicked -=> catchBall Reactivity The ifB function performs a continuous combination of control systems: control may pass freely between the systems and the predicate defining the domains is evaluated constantly. We also need committed choice – a one-way sequencing from one behavior to the next. Initial behavior Transition event New behavior FRP primitives

FRP Events: 

FRP Events Another essential FRP type: Events. An event stream represents a set of discrete occurrences in time type Event a = [(Time, a)]  idealized Events in the Robocup context: goalScored :: Event Bool -- occurs when a goal is scored -- boolean indicates scoring team Synthesize events from behaviors: predicate :: Behavior Bool -> Event () -- watch a behavior Lots of primitive FRP event functions: andThen :: Event a -> Event b -> Event b -- sequential occurrence of events

Better Abstractions: 

Better Abstractions Use until to build more powerful sequencing abstractions. Another way to define a controller: type Task a b = (Behavior a, Event b) Add a terminating event to a behavior This function performs two tasks in sequence: (b1, e1) >> (b2, e2) = (b1 `until` e1 -=> b2, e1 `andThen` e2) composability!!!

Better Tasks: 

Better Tasks This fits into a more general pattern: the monad We may also need a special type of task: the empty task. This defines no behavior – control passes to the next task immediately. However, a null task may observe the instantaneous system state Some useful null tasks: closestRobotToBall :: Task a Robot passPoint :: Task a Point2

More Monad Magic: 

More Monad Magic We can use the same monad that sequences tasks to associate tasks with sets of robots. (a state monad). This allows parallel task composition. Similar to a case statement – selected robots are passed to different tasks. Selectors have type Robot -> Bool sel1 ==> task1 ||| sel2 ==> task2 ||| rest ==> task3

Example: Delegation: 

Example: Delegation teamTask = (isRobot 1==> (liftT(annoy 5))||| isRobot 2 ==> (liftT(annoy 2))||| isRobot 5 ==> (liftT keeper) ||| isRobot 3 ==> (liftT attack) ||| rest ==> (liftT field_player))

FVision: Functional Vision: 

FVision: Functional Vision Another DSL: used for computer vision Tracks the robots and ball in the camera images Uses a large C++ library to do the “dirty work”: use of Haskell does not degrade performance Uses FRP to integrate with other parts of the system

Further Research : 

Further Research Improve basic control systems: kick ball, maintain position, block opponent Address the real time issue: the communication link between the computer and the robots has a delay associated with it, so we want to send a function from position to vector, not just the vector Planning and assessment of strategies Adaptive control systems based on observed robot behaviors

Related Work: 

Related Work The simulator we are using, JavaSoccer, Tucker Balch, CMU Behavioural Language Clay associated with the Simulator A group of Java classes that can be easily combined to create behaviour-based robot control systems. Not declarative

Conclusions: 

Conclusions Domain Specific Languages (DSL’s) are a good thing Higher order functions capture complex abstractions in a reusable way Our DSL supports rapid, reliable program development: high level programs, reusable components, safety ensured by the polymorphic type system Functional Reactive Programming is an effective way of describing interactive systems in a declarative manner. Implicit time flow is a convenient abstraction.

The Task Monad: 

The Task Monad TaskW t1 >>= u = TaskW (rs cont -> t1 rs (\s’ res -> case res of Right v -> case u v of TaskW t2 -> t2 s’cont Left l -> cont s’ (Left l))) return k = TaskW (\s c -> c s (Right k)) TaskW :: (TState -> (Tstate -> Either RoboErr a -> WheelControlB) -> WheelControlB) -> TaskW a