ibm talk3

Information about ibm talk3

Published on January 4, 2008

Author: Abigail

Source: authorstream.com

Content

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

Related presentations


Other presentations created by Abigail

The Vitamins
06. 03. 2008
0 views

The Vitamins

Yoshi Iwasaki
09. 10. 2007
0 views

Yoshi Iwasaki

Involving Teachers
23. 11. 2007
0 views

Involving Teachers

Rocks and Bauds
18. 12. 2007
0 views

Rocks and Bauds

JudyDodson BridgestoLiteracy
30. 12. 2007
0 views

JudyDodson BridgestoLiteracy

A Predator and his Prey
01. 01. 2008
0 views

A Predator and his Prey

AMPresentations
03. 10. 2007
0 views

AMPresentations

bohmer slides
07. 01. 2008
0 views

bohmer slides

zoonotic disease rodent grove
16. 11. 2007
0 views

zoonotic disease rodent grove

Joe Arata Speculative Funds
04. 10. 2007
0 views

Joe Arata Speculative Funds

boomer webcast final
29. 12. 2007
0 views

boomer webcast final

OntologySummit2007Bu ffalo
27. 09. 2007
0 views

OntologySummit2007Bu ffalo

1 M K Bansal Finance
19. 02. 2008
0 views

1 M K Bansal Finance

qmmet01
15. 11. 2007
0 views

qmmet01

The Rebel Sell
24. 02. 2008
0 views

The Rebel Sell

cietspresentationsm
10. 03. 2008
0 views

cietspresentationsm

elroy
16. 11. 2007
0 views

elroy

Tudhope
03. 12. 2007
0 views

Tudhope

L Morris
12. 03. 2008
0 views

L Morris

Prof Delanty CERC sem 3Oct2006
14. 03. 2008
0 views

Prof Delanty CERC sem 3Oct2006

hotel invest01
18. 03. 2008
0 views

hotel invest01

batlas30
21. 03. 2008
0 views

batlas30

schmitz
27. 03. 2008
0 views

schmitz

IanMidgley Unilever
07. 04. 2008
0 views

IanMidgley Unilever

Dan Sprint
30. 03. 2008
0 views

Dan Sprint

BBAhonproj
13. 04. 2008
0 views

BBAhonproj

monbaliu
07. 11. 2007
0 views

monbaliu

20051008MSR34559
04. 03. 2008
0 views

20051008MSR34559

asa 2005
28. 09. 2007
0 views

asa 2005

barnes
28. 12. 2007
0 views

barnes

avaclee
07. 01. 2008
0 views

avaclee

The Gilded Age and Progressivism
07. 12. 2007
0 views

The Gilded Age and Progressivism

language hurts ken cc
31. 12. 2007
0 views

language hurts ken cc

the gulf of naples
03. 10. 2007
0 views

the gulf of naples

07 Murray
29. 12. 2007
0 views

07 Murray

mch100a
26. 02. 2008
0 views

mch100a