ibm talk3

50 %
50 %
Information about ibm talk3

Published on January 4, 2008

Author: Abigail


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

Add a comment

Related presentations

Related pages

Inter-Cloud Mobility of Virtual Machines - IBM Research ...

Inter-Cloud Mobility Empirical Study IBM Israeli Evaluation – Haifa ... Microsoft PowerPoint - session1_talk3_Systor11-Inter-Cloud-VM-Mobility.ppt
Read more

Trading off Quality for Throughput Using Content ...

Microsoft PowerPoint - session2_talk3_feitelson.pptx Author: yairh Created Date: 6/30/2011 13:22:33 ...
Read more

Daniel Turner | LinkedIn

View Daniel Turner's professional profile on LinkedIn. LinkedIn is the world's largest business network, helping professionals like Daniel Turner discover ...
Read more

BCGS Intensive Week Course: - Institut für Kernphysik der ...

Among these are IBM with inclusion of other bosons (SDG, SPDF, etc.) (Tuesday/Wednesday) ... K. Nomura (Talk3) "Microscopy" J. Jolie (Talk4) "Intruders"
Read more

IBM Notes and Domino Application Development wiki: XPages ...

Social business wiki for IBM Notes/Domino application development and IBM Domino Designer product documentation and community content
Read more

Google Talk - Wikipedia, the free encyclopedia

Google Talk is an instant messaging service that provides both text and voice communication. The instant messaging service is colloquially known as "gtalk ...
Read more

Dani Turner profiles | LinkedIn

View the profiles of professionals named Dani Turner on LinkedIn. There are 25 professionals named Dani Turner, who use LinkedIn to exchange information ...
Read more

Daniel Turner Profile – Deutschland | LinkedIn

Business Development Director at FutureLogic, Inc., SVP Operations at Talk3, ... IBM SSM, UMIST, MCSE, The University of Manchester Zusammenfassung
Read more

Top 25 Danny Turner profiles | LinkedIn

Danny Turner profiles. ... SVP Operations at Talk3, ... Project Management at IBM, Infrastructure Specialist at IBM: Education:
Read more

Top 25 Daniel Turner profiles | LinkedIn

There are 1,175 professionals named Daniel Turner, ... SVP Operations at Talk3, ... Education: The University of Manchester, IBM SSM, MCSE, UMIST: Summary:
Read more