Michael Beetz
email: beetzm@in.tum.de

Freek Stulp
email: stulp¡@in.tum.de

Alexandra Kirsch

Armin Müller

Sebastian Buck

Autonomous Robot Controllers Capable of Acquiring Repertoires of Complex Skills

Due to the complexity and sophistication of the skills needed in real world tasks, the development of autonomous robot controllers requires an ever increasing application of learning techniques. To date, however, learning steps are mainly executed in isolation and only the learned code pieces become part of the controller. This approach has several drawbacks: the learning steps themselves are undocumented and not executable. In this paper, we extend an existing control language with constructs for specifying control tasks, process models, learning problems, exploration strategies, etc. Using these constructs, the learning problems can be represented explicitly and transparently and, as they are part of the overall program implementation, become executable. With the extended language we rationally reconstruct large parts of the action selection module of the AGILO2001 autonomous soccer robots.

Introduction

Programming sophisticated low-level control skills as well as action selection strategies for autonomous robots acting in dynamic and partially observable environments is both tedious and error prone. Autonomous robot soccer, which has become a standard "realworld" test-bed for multi robot control, provides a good case in point. In robot soccer (mid-size league) two teams of four autonomous robots -one goal keeper and three field players -play soccer against each other. The key characteristics of mid-size robot soccer is that all sensing and action selection is done on-board.

Competent soccer play entails, besides other capabilities, the skillful execution of various navigation tasks such as defending, dribbling, moving past opponents, and intercepting the ball. To realize them, robots could use computational means to infer which control signal should be issued to arrive at a desired state, how long it will take to get there, and how promising it is in the current situation to try to arrive at this state.

Because of the dynamical and adversarial nature of a soccer play and physical subtleties such as friction on different surfaces and the weight of the robot, programming procedures for these reasoning tasks is very difficult. An attractive alternative is the development of control systems that can acquire and adapt such procedures automatically. Obviously, such a control system must learn at various levels of abstraction. It must learn process models from sensory data such as the effects of control signals on the dynamical state, and optimize control laws, e.g. for approaching the ball. It must acquire models of control routines including their success rates and time requirements to decide whether or not to go for a ball or defend the goal. Finally, it must learn the situation-specific selection of appropriate actions.

In current practice, such learning tasks are typically considered and solved in isolation. A programmer gathers a set of examples for learning or provides an exploration strategy. Then a learning system, a feature language in which the acquired data are to be encoded, and a suitable parameterization of the learning system are selected. Subsequently, the learning step is executed, the learned routine transformed into an executable piece of code, and provided as part of a software library. The controller can then use the learned routine by calling it as a subroutine. This approach has several disadvantages: the learning steps themselves are undocumented and not automatically executable, and therefore difficult to reproduce.

In this paper, we extend an existing control language to automate this process. Using the constructs of this language, the system model can be specified, and the learning problems can be represented explicitly and transparently, both becoming an integrated part of the overall program. Therefore, the learning problems become executable, documentation of models is integrated in the program, modularity is higher, and analysis of the system is simplified.

Several programming languages have been proposed and extended to provide learning capabilities. Thrun [START_REF] Thrun | Towards programming tools for robots that integrate probabilistic computation and learning[END_REF] has proposed CES, a C++ software library that provides probabilistic inference mechanisms and function approximators. Unlike our approach a main objective of CES is the compact implementation of robot controllers. Programmable Reinforcement Learning Agents [START_REF] Andre | Programmable reinforcement learning agents[END_REF] is a language that combines reinforcement learning with constructs from programming language such as loops, parameterization, aborts, interrupts, and memory variables. A difference with our method is that learning tasks can also be specified in our language, and that the learning methods are not confined to reinforcement learning only.

In the remainder of this paper we proceed as follows. The next section describes how process models can be specified. In section 3 it is shown how learning problems can be specified, and in section 4 we give a case example: the AGILO2001 controller. We conclude with a detailed outlook on our future research investigations.

Modeling the System

In this section we specify models of different components of the robot and its environment, and show how they can be made explicit in our language. The first class of models we present are process models, such as the robot's dynamics and sensing processes. The second class models the robot's control routines.

Specifying the Environment Process

define controlled process robot field process static environment field model environment process ball proc., robot proc., team-mate proc. ¢ ¤£ ¥ ¦£ § , opponent proc. ¢ ¤£ ¥ ¦£ § ¨£ © sensing process ¨ ¤ camera-image odometry-reading ! ! " # $

The construct above specifies that the "robot field process" is a controlled process (we use the dynamic system model, described in [START_REF] Dean | Planning and Control[END_REF]), consisting of a static field model and environment and sensing process. These two processes can themselves be decomposed into subprocesses. In the model of the AGILO RoboCup control system the environment process consists of the dynamics of the robot, which specifies how the control inputs change the physical state of the robot. The other subprocesses of the environment process are those that change the physical states of the team mates, the ball, and the opponent robots. All these processes are largely independent of each other. The only interactions between them are collisions and shooting the ball.

By using this construct the model of the environment is an explicit part of the overall program. This ensures that documentation about the model is integrated, and that modularity of different processes is enforced. Not only does this construct model the real environment, it can also be used as an environment simulator specification. To realize this simulator, the process models need to be implemented. A straight-forward method of realizing this is by manually implementing procedures for each process. If these process models suffice for predicting the effects of control signals on the game situation then they constitute an ideal simulator for the system. In section 3 it will be shown that by using learning task constructs, the manual implementation can be replaced by a learning procedure, which can be integrated into the overall program as well.

Specifying the Control Process

In this section we provide the control system with models of its control routines. These models enable the robot to do more sophisticated action selection and thereby improve its behavior with respect to the given performance measure. We provide this model in two pieces. First, the control task that specifies what has to be done and second, the control routine that specifies how it has to be done. The rationale behind separating these two aspects is that a task can be accomplished by different routines that have different performance characteristics.

Control Tasks specify what the robot should be capable of doing. For example, the robot should be capable of going to the ball, intercepting a ball, and defending. A control task can be specified in two ways: first, we can specify it using a start state and a description of goal states. An example of such a control task is the following one: reach the position of the ball facing the opponent goal, which we represent as . For example, we might constrain this control task to situations where the ball is not in the own penalty area. In addition, we can specify a probability distribution over the possible set of tasks. This probability distribution affects the expected performance of the control routines.

An alternative way of stating a control task is to specify it using the start state and an objective function, a performance measure that the robot should try to maximize. For example, for attacking, an appropriate performance measure might be the expected time needed to shoot a goal, which should be minimized. . The process signature indicates that the current dynamic state and the desired dynamic state are mapped into control inputs for the translational and rotational velocity of the robot. The control process specification then states when the control task should be activated and the different possible outcomes of performing the control task.

Control Routines specify how the robot is to respond to sensory input or changes in the estimated state in order to accomplish a given control task. We might have different routines for a given control task, which have different performance characteristics. Control routines first of all consist of an implementation, a procedure that maps the estimated state into the appropriate control signals. Besides the implementation we have the possibility to specify models for the control routine, encapsulating the procedural routine within a declarative construct which can be used for reasoning and manipulating. Suppose we had a model consisting of decision rules that can identify situations in which the control routine is very likely to succeed and very likely to fail. We could then apply these rules in order to decide whether to activate the routine in the current situation or terminate it if the routine is likely to fail. This is not possible with only a procedural representation of the control routine.

Adding Learning Capabilities

In the last section we have specified process models and implemented them as procedures. However, it is often difficult and tedious to program them manually. In this section we will describe how the corresponding learning problems and the mechanisms for solving them can be specified. There are a number of program pieces that can be learned rather than being specified by programmers. In our robot soccer application, the robot learns, for example, the process model for its dynamics. Also, there are many opportunities for learning the implementation as well as the models of control routines.

We will restrict ourselves to learning problems that can be solved by function approximation. In particular, we will look at problems that can be learned by artificial neural networks and by decision tree learning algorithms. Our primary example will be learning how to achieve a given dynamic state, which is representative for learning in the context of control routines.

To state learning problems we must provide several pieces of information. The type of function that is to be learned, whether it is a process model or a control task. We must also specify the robot to be controlled and the environment it is to act in. In addition, the learning problem specification contains a specification of a problem specific learning system, and the data gathering process. This information is provided using the macro define-learning-problem.

define learning problem achieve-dynamic-state control-routine achieve-dynamic-state-3 control-task achieve ( % '& ( F& 1 3 "4 B4 6 78 ( 08 1 3 "4 B4 6 7D v( FD G PI ¨1 3 "4 B4 S

) dynamic system agilo-robot-controller data-collector achieve-state-data-collector learning-system achieve-state-learner

The learning problem specification shown above specifies these information pieces for the task achieve dynamic state. In the remainder of this section, we introduce the representational structures for specifying the different components of learning problems and then discuss issues in the implementation of these constructs.

Specifying Data Collection

The first step in learning is the data collection. To specify data collection we must state a control task or sample distribution and we have to provide monitoring and exception handling methods for controlling data collection. CLIP [START_REF] Anderson | A toolbox for analyzing programs[END_REF] is a macro extension of LISP, which supports the collection of experimental data. The user can specify where data should be collected, but not how.

In order to acquire samples we have to define a sample distribution from which samples are generated. During data collection the perception, control signals, and control tasks of each cycle are written to a log file. The data records in the log files can then be used for the learning steps. The task distribution specification above defines a distribution for the initial state consisting of the robot's pose and translational and rotational velocity, as well as the goal state of an episode, which consists of the desired translational and rotational velocity. The body of the episode consists of setting the robot in its initial state and then setting the desired dynamic state as a goal for the controlled process.

The data collection cycle starts with an initialization phase in which a task is sampled from the task distribution. In the distribution above this is the setstate command in the with setup statement. The data collector monitors the initialization to detect whether or not it has been successful. Unsuccessful initialization is particularly likely when the learning task is performed using the real robots. Upon successful initialization the data collection phase is activated. In the data collection phase the perception and control signals are collected. The data collector then detects the end of the episode and decides whether or not the episode is informative and should be recorded.

Thus, in order to collect data reliably and efficiently it is necessary to specify special purpose code for the initialization phase, for failure handling, and resetting the robot. These code pieces can be provided using the define data collection functions .

Specifying Learning Systems

Learning problems can be solved with very different learning systems such as artificial neural networks or decision tree learners. In order to specify a task-specific learning systems three pieces of information must be provided. First, we have to specify how the collected data are to be transformed into patterns that are used as input for the learning system. An example is the transformation of global coordinates to an robot-centric coordinate system. Second, a function for parameterizing the learning system. For an artificial neural network for instance we have to define the topological structure of the network. Finally, we must provide a function that transforms the output of the learning system into an executable function that can be employed within the robot control program. Thus, the input patterns for the achieve-dynamic-state control task can be defined as follows:

define state space achieve-dynamic-state input-features ( ( o G 'p "3 !q t (percept:

o G 'p "3 :time u )) ( o G 'p "3 !q r goal-state: o G 'p "3 ) ) output-values ( ( o G 'p ¨3 !q v (percept: o G 'p ¨3 :time w Pu ix Fy Hz )) ) output-function ( o v float)
The macro declares the training pattern to consist of the feature o G 'p "3 !q t , which is taken to be the , is the translation velocity of the subsequent entry in the log file. The output of the learned function will be o G 'p "3 !q v .

From Partial Specification to Executable Program

We have implemented our representational structures using LISP's macro facilities and provided them in the context of Structured Reactive Controllers (SRCs) [START_REF] Beetz | Structured Reactive Controllers -a computational model of everyday activity[END_REF]. The LISPbased parts are equipped with an abstract robot interface consisting of C libraries loaded as shared objects. The system uses shared memory communication as a coupling to the low-level control processes. To date, we have provided the functionality of two learning systems: the decision tree learning algorithm C4.5 and the Stuttgart Neural Network Simulator (SNNS).

An important implementational aspect is how we get from declarative problem specifications to executable and effective learning processes. For this and other purposes control routines, process models, and control routine models are represented as first class objects that computer programs can reason about and manipulate. One property of these objects is that they can have an implementational status, such as to-be-learned. The distinct characteristic of this program is that in the beginning it only partially specifies the behaviour, leaving unspecified behaviour to be learned at a later stage.

Transforming this partial specification to an executable control program proceeds in three steps. In the first phase a problem collector traverses the top-level control routine and collects all references to procedures with the status to-be-learned and stores them in the set of learning problems. In the second phase, the routines are learned. We consider a routine as learnable if it is to-be-learned and does not call any code to-be-learned. Therefore, the procedures are learned in an order that respects the dependencies between them, until all routines are learned. Finally, the complete program can be run to produce the behaviour, for instance playing robot soccer.

A Rational Reconstruction of the AGILO2001 Controller

With the extended language we have rationally reconstructed large parts of the action selection module of the AGILO autonomous soccer robots, with processes, data collection, learning system generation specified in constructs. The control program resulting from this reconstruction can automatically learn a repertoire of routines for playing robot soccer competently. In this section the learning process is demonstrated.

In the bootstrap learning phase the first learning task that is tackled is the learning of the robot dynamics. This learning task acquires a process model for the environment and does not depend on the solution of any other learning problems. To learn the dynamics we use the log files obtained from earlier RoboCup games and transform them into a pattern file for the learning system. For learning, we train an artificial neural network using the SNNS system in order to approximate the mapping:

W u C{ |u C} H { | u V H W u C{ |u C} H v .
In [START_REF] Buck | A Multi Robot Simulation Environment for Learning Cooperative Behavior[END_REF] this procedure is described in more detail. The next learning task that the robot can address is how navigation tasks are to be achieved. We have already seen in the specification of this task in section 2.2. This is learned in a simulated environment, which only requires the learned robot dynamics. To solve the learning task as a function approximation problem we provide the robot with streams of control signals that generate good navigation trajectories. From this data the robot learns the mapping

W u C{ |u C} p ¦p " ¤ G W u C{ |u C} r I ¦3 R4 { Ru V ¤ H p ¨p ¨ ¤ G
, using a multi layer neural network. For a more detailed description see [START_REF] Buck | Planning and Executing Joint Navigation Tasks in Autonomous Robot Soccer[END_REF].

Once the controller can execute the navigation task, the robot learns a model of the task. Given the simulated dynamics and the controller learned in the two previous steps, the robot is given many automatically generated navigation tasks to execute. The duration of the task is recorded, and this training data is used to learn the mapping

W u C{ |u C} p ¦p " ¤ G W u C{ Au C} r I ¨3 "4 u V } u H } u C}
, again using a multi layer neural network. This mapping is necessary to coordinate the behaviour of our robots, the next step in creating the complete AGILO controller. How this is done is discussed in [START_REF] Buck | Planning and Executing Joint Navigation Tasks in Autonomous Robot Soccer[END_REF].

Since all these learning tasks are specified with constructs in the program, adaptation of the program is simplified. Learning tasks can be exchanged, without requiring a redesign of the program structure. The program just needs to check if any constructs are to-be-learned, and relearn them and any depending constructs. Another case example that shows the strength of making learning tasks explicit is when hardware is upgraded. Recently our robots have received new control-boards. Instead of having to repeat all learning steps to model these new boards manually (involving undocumented scripts, manual data copying and transformation, and so forth), we only have to provide the system with a log-file, and set all relevant learning tasks to to-be-learned. The dependencies between the learning tasks ensure that first the robot dynamics will be learned. Given these dynamics, which can be used in the simulator, the navigation tasks can be relearned. Given the navigation routines, models of the navigation routines can be learned, and so on, until the complete executable AGILO2001 controller is acquired. We are currently testing these procedures. Furthermore, the scope of learning tasks is being extended beyond the AGILO2001 controller, to include additional control tasks such as dribbling with fake movements, defending, shooting, and others. In addition, we are starting to tackle reinforcement learning problems.

Conclusions

In this paper, we have extended a control language with constructs for explicitly representing (1) the physical system that is to be controlled and (2) the learning problems to be solved. In the extended language entities such as control tasks, process models, learning problems, and data collection strategies can be represented explicitly and transparently, and become executable. In the learning and execution phase, the entities are first class objects that control programs cannot only execute but also reason about and manipulate. These capabilities enable robot learning systems to dynamically redesign learning problems. We have also sketched the implementation of the learning phase and showed how a bootstrap learning method can automatically complete a partially defined control program by solving the stated learning problems. The extensions that we have presented are expressive enough to rationally reconstruct most of the AGILO2001 action selector. Other complex control systems need to be implemented using our approach and the conciseness and expressivity of our constructs need to be assessed and analyzed. We are just starting to incorporate optimizing learning techniques such as reinforcement learning into our approach.

We see the main impact of our framework along two important dimensions. From a software engineering perspective, the language extensions allow for transparent implementation of learning steps and abstract representation of complex physical systems. These aspects are typically not adequately addressed in current control systems, which makes them hard to understand and adapt to new requirements and conditions. The second dimension, which we find much more exciting, is the use of the framework as a tool for investigating more general and powerful computational models of autonomous robot learning. The programmability of learning systems, the modifiability of state representations, the possibility of reparameterizing learning systems, and the executability of learning specifications within the framework enables us to solve complex robot learning tasks without human interaction. The framework thereby enables us to investigate adaptive robot control systems that can autonomously acquire sophisticated skills and competent task control mechanisms for a variety of performance tasks.

%

  '& )( 0& 21 3 "4 54 76 78 9( @8 A1 3 "4 B4 C6 ¦D E( FD HG PI ¨1 Q3 R4 B4 TS . The set of possible control tasks can be constrained as U % 'V CW A6 CX YW HS !`V CW )a cb ed gf gs a Fh id qp

  define task distribution achieve-dynamic-state with global vars translation-tolerance n 0.03 max-time-steps n 20 for initial state % P& i6 ¦8 26 ¦D Y6 7o G 'p "3 6 ¦o p ¨I 7G

  o G 'p ¨3 of the percept component of a log file entry and o G 'p "3 !q r that is the o G 'p ¨3 of the goal state of the log file entry. The output value of the pattern, called o G 'p "3 !q v

  Let us consider, as an example, the control task specification shown above. The task specification states the desired values for the state variables

	j fails (navigate g ¤r ts H ¤ 7 R m ¤h )
	active (navigate g ¤r ts H C m C R ¤h ) i r ts 2 ¤ y ¤ u 0r ts H C R H
	j	succeeds (navigate g ¤r ts H ¤ 7 R m ¤h )

control task achieve-dynamic-state task specification r ts vu ws yx ' R P u w Hx ' R T ¤ u g 7x ' R process signature r ts 2 Q Y ¤ H r ts H C R H dr te f ¤ ¤e f C 7 control process specification goal g ¤r ts ¤ ¤ ¤h 2i achievableg ¤r ts C ¤h kj active (navigate g ¤r ts C ¤h ) goal g ¤r ts ¤ ¤ ¤h 2i 9l achievableg ¤r ts ¤ ¤ ¤h vj fails (navigate g ¤r ts ¤ ¤ ¤h ) active (navigate g ¤r ts H C m C R ¤h ) i timed out & , 8 , and D


Armin Müller

Alexandra Kirsch

Michael Beetz

Object-oriented Model-based Extensions of Robot Control Languages

More than a decade after mobile robots arrived in many research labs it is still difficult to find plan-based autonomous robot controllers that perform, beyond doubt, better than they possibly could without applying AI methods. One of the main reason for this situation is abstraction. AI based control techniques typically abstract away from the mechanisms that generate the physical behavior and refuse the use of control structures that have proven to be necessary for producing flexible and reliable robot behavior. The consequence is: AI-based control mechanisms can neither explain and diagnose how a certain behavior resulted from a given plan nor can they revise the plans to improve its physical performance.

In our view, a substantial improvement on this situation is not possible without having a new generation of robot control languages. These languages must, on the one hand, be expressive enough for specifying and producing high performance robot behavior and, on the other hand, be transparent and explicit enough to enable execution time inference mechanisms to reason about, and manipulate these control programs. This paper reports on aspects of the design of RPL-II, which we propose as such a next generation control language. We describe the nuts and bolts of extending our existing language RPL to support explicit models of physical systems, and object-oriented modeling of control tasks and programs. We show the application of these concepts in the context of autonomous robot soccer.

Introduction

Robot control languages have an enormous impact on the performance of AI-based robot controllers. The languages allow for explicit and transparent representation of behavior specifications for reasoning and execution time program manipulation, and they provide the control structures for making the robot behavior flexible, reliable, and responsive. Despite their importance research on the design of robot control languages that enable intelligent robot control is largely neglected in AI -primarily for historical reasons.

As the predominant software architecture for autonomous robot control most researchers have used layered architectures, most notably the 3T architectures [START_REF] Thrun | Map learning and high-speed navigation in RHINO[END_REF]. Characteristic for these layered software architectures is the use of multiple control languages: a programming language for the low-level reactive control and a very simple high-level language for strategic planning. This way the planner can still nurture the illusion of plans being sequences of plan steps and many existing planning techniques carry over to robot control more or less the way they are. To bridge the gap between the partially ordered sets of actions (goal steps) and the low-level feedback control routines most software architecture use an intermediate control layer. In this intermediate layer an interpreter for a reactive plan language, such as RAP [START_REF] Firby | Adaptive Execution in Complex Dynamic Worlds[END_REF] or PRS [START_REF] Ingrand | An architecture for real-time reasoning and system control[END_REF], takes the high-level plan steps, selects methods for carrying them out based on sensor data, and executes them in a robust manner.

Unfortunately, this layered abstraction of robot control comes at high cost. The planning mechanisms cannot diagnose the behavior produced by a given plan because the behavior producing mechanism is much more sophisticated than assumed by the planning mechanisms. In addition, the planning mechanisms cannot exploit the variety of control structures offered by reactive plan languages to produce better behavior.

Let us illustrate this point using the following example taken from the autonomous robot soccer domain. A robot is to score a goal. An AI planner would typically produce a simple two step plan: (1) get the ball; [START_REF] Beetz | Structured Reactive Controllers[END_REF] dribble it into the goal, because ball possession is a precondition for scoring. The navigation and the dribbling actions are considered as atomic black boxes. Unfortunately, these mechanisms do not allow for the generation of high performance plans with high scoring probability such as the one depicted in Figure 1(right). To compute such a high performance plan planning mechanisms have to tailor the parameterizations of the individual actions using accurate causal and physical models of the control routines they use. generated using causal models optimized using projection functions

Belief State Intention

Valid Plan Optimized Plan "Score Goal" As plan-based robot control systems come of age and are applied to real world tasks a new generation of software architectures arises that are capable of dealing with these problems. These second generation software architectures share a number of important principles. These shared principles include (1) lightweight reasoning is embedded into the robot control languages; (2) the architectures invite programmers to specify models of the robot and its environment explicitly within the program code; (3) have much richer languages for the specification of goals in terms of constraints on the values of state variables.

In our research group we are currently working on the next generation of the robot control/plan language RPL [START_REF] Mcdermott | A Reactive Plan Language[END_REF] called RPL-II. RPL-II allows for the explicit specification and representation of robot learning problems [START_REF] Beetz | Rpl-learn: Extending an autonomous robot control language to perform experience-based learning[END_REF], for the specification of explicit robot and environment models, is object-oriented and supports the specification of specialization hierarchies for control tasks and routines and reasoning about them. RPL-II is an industrial strength robot control/plan language. It is implemented unlike its predecessor on a public domain CommonLisp using state of the art software tools such as Corba, UFFI, etc. RPL-II is applied to a variety of control tasks with different characteristics including mid-size robot soccer, a simulated household robot, and a robot assistant in an intelligent camera-equipped office environment.

This paper focuses on a particular aspect of the design of RPL-II, namely the representation and specification of the system that the controller controls and the control tasks that it performs. In a companion paper [START_REF] Beetz | Rpl-learn: Extending an autonomous robot control language to perform experience-based learning[END_REF] we have described the new language features that support experience-based learning. The main contributions of the paper are the means for specifying state variables and their management, control tasks and control routines, and object oriented programming.

We demonstrate the application of these mechanisms to the implementation of our next generation controller for autonomous robot soccer. The implementation results in control programs that make extensive and explicit use of learning mechanisms and routines that can be much better reasoned about and transformed. This is primarily achieved through the explicit representation of physical entities and control tasks and the reasoning about them.

The remainder of the paper is organized as follows. In section 2 we describe the problems we encountered with our former control program for the AGILO soccer robots and sketch the ways we want to solve them. Section 3 introduces the basic concepts for model-based reasoning about physical control tasks. The use of these concepts is then demonstrated in the sections 4 and 5. We conclude with our next intended extensions of RPL-II, a discussion of related work, and our conclusions.

Languages at the Reactive Layer

The reasons why we want to use a model-based, object-oriented approach in structuring our control programs, are our experiences with former controllers of the AGILO soccer robots. [START_REF] Beetz | The AGILO robot soccer team -experience-based learning and probabilistic reasoning in autonomous robot control[END_REF] Let us therefore sketch how the controllers worked, which problems occurred and the conclusions we draw from them.

The control program ran in a low-level control loop that (1) updates the world model (section 2.1) and (2) chooses a command (section 2.2) in every time step (every 0.01 sec).

State representation

We need a set of variables containing information about the most likely current state of the world. We call this information "belief state". The belief state is represented in a class "world model", that provides variables and functions for any value the robot might want to know. It is not possible to differentiate between -constant values (that would actually deserve the name "world model"), -values taken from the percept or belief state vector, and -values calculated from the belief state and world model. So there is a representation of the state of the world, but with several drawbacks. The variables representing the state are not related to any physical values. In different parts of the program variables with different names, but the same physical meaning can occur. The orientation of the robot might in one place be called phi, in another place phi-deg. On the other hand does the same variable name not necessarily denote the same physical value. The variable pos-x can at one time express the robot's position, at another time the position of the ball.

Besides, the robot and the environment are not represented explicitly. When starting the robot in a certain environment the right configuration file has to be loaded and constant values are set. So we have just variables filled with values that have apparently nothing to do with the outside world.

Another problem is the heterogeneity of measuring units. This is especially hard when it comes to angles. Sometimes the value is given in degrees, sometimes in radian measure. In the action selector it is quite save to assume degrees, but there is no standard if degrees range from ¢¡ to £ ¥¤ ¥¡ or from ¦ ¨ § © ¥¡ to § © ¥¡ .

Action Selection

Figure 2 shows a simplified extract of our old action selection routine. As is easily visible, there is only procedural knowledge in the controller. The information exchange between calling and called procedures is done by passing a variable param. The value(s) of this parameter sometimes denote the goal, sometimes a parameterization of the called function.

Furthermore the structure of the code seems very arbitrary. The purpose of the first three if-conditions is to trap failures. Then a more interesting part follows which decides what to do whenever the robot has the ball. Then again we have two failure conditions testing if the robot is in one of the penalty areas. Here we can see another problem. The reaction of being in the own penalty area or in that of the opponent team is almost the same and could be done by the same or a related function.

So in the end only three of eight cases build up the real controller code. The rest is only there for trapping failures. Even worse, the interesting parts are spread over the code and intercepted by failure testing. It is hopeless to reason about the best action, when there is no difference between failure trapping and real action selection.

Also the granularity of decisions seems ill-founded in our old controller code. When the robot has the ball, all we want to do is getting the ball somehow into the goal. Here the controller already decides how to do this (by dribbling the ball into the goal, kicking it or passing it to another player).

Another nuisance of our former controller is that it works in single time steps only and the decisions are purely reactive.

state representation with globally accessible state variables 2. goal representation as constraints over state variables 3. control tasks and control routines arranged in an object hierarchy

We use the robot control language RPL (section 3.1), that provides constructs for monitoring failures while performing an action and parallel execution of processes. So now we think more in terms of actions than in terms of low-level commands and control loops.

For the representation of the robot's belief state we use globally known state variables that are described in more detail in section 3.2. Every variable corresponds to a physical value. We have not yet approached the representation of measuring units, although it should not be difficult within our framework.

The goal is now specified explicitly, tightly coupled to the state variables (section 3.3). We regard a goal as an intention how the world should be changed.

Finally, we require means of how to reach a given goal from a certain belief state. Our control procedures are structured along two lines, an object-oriented inheritance hierarchy and a calling hierarchy involving two classes of control procedures (section 3.4). We represent procedures as first-class objects, which allows for the specification of relevant calling parameters. Thus we can maintain a uniform calling mechanisms for all procedures. Inheritance is also an important factor when it comes to representing similarities between procedures. This makes the implementation very structured and concise.

To structure the calling hierarchy we introduce two classes of procedures, control tasks and control routines. A skill like "get-ball-into-goal" is implemented as a control task. The different possibilities to fulfill the job like "dribble-ball-into-goal" or "kickball-into-goal" are represented as control routines. Control tasks and routines are called alternatively. The success and failure testing is completely done in the control task, as well as the choice of the appropriate routine in the current situation.

The Reactive Plan Language RPL

The robot's plans are implemented in RPL (Reactive Plan Language) [START_REF] Mcdermott | A Reactive Plan Language[END_REF], which has been successfully employed in different projects [START_REF] Beetz | Integrated plan-based control of autonomous service robots in human environments[END_REF][START_REF] Beetz | Plan-based Control of Robotic Agents[END_REF][START_REF] Beetz | Structured Reactive Controllers[END_REF]. RPL provides conditionals, loops, program variables, processes, and subroutines as well as high-level constructs (interrupts, monitors) for synchronizing parallel actions. To make plans reactive and robust, it incorporates sensing and monitoring actions, and reactions triggered by observed events.

Connecting Control Routines to "Sensors" Successful interaction with the environment requires robots to respond to events and asynchronously process sensor data and feedback arriving from the control processes. RPL provides fluents, registers or program variables that signal changes of their values. Fluents are used to store events, sensor reports and feedback generated by low-level control modules. Moreover, since fluents can be set by sensing processes, physical control routines or by assignment statements, they are also used to trigger and guard the execution of high-level control routines.

Fluents can also be combined into digital circuits that compute derived events or states such as the robot's current distance to the ball. That fluent would be updated every time the position of the robot or the ball changes, since it is calculated out of the respective fluents.

Fluents are best understood in conjunction with the RPL statements that respond to changes of fluent values. The RPL statement whenever F B is an endless loop that executes B whenever the fluent F gets the value "true." Besides whenever, wait for(F ) is another control abstraction that makes use of fluents. It blocks a thread of control until F becomes true.

Behavior Composition sources use control structures for reacting to asynchronous events, coordinating concurrent control processes, and using feedback from control processes to make the behavior robust and efficient. RPL provides several control structures to specify the interactions between concurrent control processes (figure 3). The control structures differ in how they synchronize processes and how they deal with failures.

The in parallel do-construct runs a set of processes in parallel and fails if any of the processes fails. The second construct, try in parallel, can be used to run alternative methods in parallel. The compound statement succeeds if one of the processes succeeds. Upon success, the remaining processes are terminated. Similarly try in order executes the alternatives in the given order. It succeeds when one process terminates successfully, it fails when all alternatives fail. with policy P B means "execute the primary activity B such that the execution satisfies the policy P." Policies are concurrent processes that run while the primary activity is active and interrupt the primary if necessary. Additional concepts for the synchronization of concurrent processes include semaphores and priorities.

State Representation

We represent the state of the world by globally declared variables. Figure 4 shows the class hierarchy of these variables. Every value that is globally known throughout the system is called a global value. Every variable has a name and a (current) value. The world consists of values changing over time and values that remain constant. Constants are initialized when the system is started and represent the world model (section 4).

More interesting are state variables. Their value is represented as an RPL fluent, because it changes over time. Apart from being informed when a state variable has changed, it is often necessary to have access to former values. A recording state variable keeps a history of its past values. The history values can be accessed by the same function get-value that is used to obtain the current value of a state variable by specifying an additional parameter giving the number of steps we want to look back in time. With these specifications we can now define observable state variables that represent our percept or belief state and controllable state variables representing the command. An observable state variable has an additional parameter for setting a goal value. This is explained in more detail in section 3.3.

The representation of the plain percept as state variables is usually not sufficient to make adequate decisions. For example we might want to react if a player is leaving the boundary of the soccer field. Or maybe we want to know if the robot has been stuck over a longer period of time. Therefore we introduced the concept of derived state variables. From the outside, derived state variables are accessed just like observable state variables. But instead of keeping a history we remember the components and the function that produces the value of the derived state variable taking the component state variables as input. When a past value is accessed it is calculated from the history elements of the components.

As an example we have a look at the state variables in our soccer robots. The observable state variables include pos-x, pos-y and phi-deg which represent the x-and y-coordinates of the robot and its orientation as well as ball-x and ball-y denoting the position of the ball. The controllable state variables are c-rotation, c-translation, which set the robot's rotational and translational velocities, and kick, a boolean variable indicating whether to use the kicking device. Now we can define a derived state variable denoting the robot's distance to the ball: make-instance derived-state-var name: distance-to-ball elementary fluents: pos-x, pos-y, ball-x, ball-y combination function:

¡ pos-x ¢ ball-x £ ¥¤ §¦ ¡ pos-y ¢ ball-y £ ¨¤
The fluent of the variable distance-to-ball depends on the state variables given in elementary fluents. The combination function calculates the current distance of the robot and the ball.

In order to test whether the robot is approaching the ball, we only need to check whether the distance to the ball has decreased: fluent approaching-ball (get-value(distance-to-ball, t) © get-value(distance-to-ball, t-1))

Since distance-to-ball is not a recording state variable, it does not have a history of its own. As the components and the function for obtaining the value are known and the components have a history, older values of distance-to-ball can be calculated.

Goals

Up to now our controller follows the very simple policy of our former control program described in section 2. In the future we would like to use a belief-desire-intention structure for the representation of top level goals or intentions (section 6). On the lower level we have to address the issue of how to tell a routine what to do.

There are two points of view for representing goals. First, we could order a routine to do something for us like "go to position 1.0, -1.5 ". So we have to pass a data structure that the routine must know how to interpret. The drawback of this idea is that there is no explicit relationship to the state variables pos-x and pos-y. The routine just knows that when these two state variables have the value of the goal specification the work is done. Now the situation can also be seen as follows. Our control program wants to alter the world in a certain way, it might for example want to be in a state where the robot is at position 1.0, -1.5 . It can now tell the corresponding state variables that it would like to have them changed to a different value. Then the controller calls a routine that is best fit to produce the desired state from the current situation. The called routine looks up the goal values of the state variables and tries to reach them.

Procedures

To support an explicit representation of the agent program, we describe procedures as first class objects, so that we can reason about aspects such as performance measures or we can find out if a procedure has yet to be learned. Figure 5 shows the basic class hierarchy of procedures. A procedure is any kind of function. At the moment, the for us most interesting subclass of procedure is a control procedure. A control procedure maps recent percepts to a command. Other kinds of procedures like environment processes, that map a command to a world state, might play a larger role in the future when we will model environment and perception processes.

For a good robot behavior we found it necessary to introduce two concepts of control procedures, control tasks and control routines. A robot should have certain skills, in the robot soccer domain we need skills such as dribbling or scoring a goal. These skills are called control tasks. Usually there are different ways to perform a skill. For example, in order to score a goal the robot might use its kicking device or dribble the ball into the goal. These implementations are called control routines. The job of the control task is to decide which control routine should be called in the current situation. This decision is based on models of the control routines that predict the time needed to fulfill a task or the probability of being successful.

Figure 6 shows a typical pattern of how control tasks and routines call each other. The task of scoring a goal can be achieved by two routines. One of them kicks the ball into the goal, the other one dribbles the ball to a point inside the goal. This second routine can be implemented like this: control routine dribble-ball-into-goal p := find-goal-point() adjust-goal(pos-x p.x, pos-y p.y) execute(dribble)

We see that we need the task of dribbling in order to fulfill our goal. Therefore the control task dribble is executed, which can again be implemented by different control routines.

The "procedures" we are talking about are actually objects, the function that is really running is the generic function execute. With an object oriented approach we use inheritance mechanisms to get compact and concise implementations of the execute methods. This object oriented approach is especially useful in the domain of robot soccer where almost every action comes down to navigation. So by using an object hierarchy we save a lot of work and redundancy.

Control Tasks Every skill is modeled as a control task. It should know when it has succeeded and when a failure has occurred and either react to it or abort execution. A special case of a failure is the exceeding of time resources. Since a control task's job is to choose the best control routine, it must know which control routines are available. All this information is given in the class definition:

class control task success failure time-out available routines
In most cases the control task will choose a control routine and check for failures or success during the execution. Such a method is shown in figure 7. What remains to do is the specification of the method choose-control-routine, which has to be implemented for each control task using models provided by the control routines. Control Routines are implementations of a control tasks. Since a control routine is always called by a control task, we don't have to worry about success or failure conditions. In both cases, the routine is interrupted by the control task. If there are errors the control task cannot detect, we can check them in the execute function of the control routine and return a fail command.

A control routine should not only reach a given goal state, it should also be able to predict how long it will take to reach this goal, what the accuracy of the solution will be or the probability of being successful at all. Thus, a control routine requires not only an execute method, but also methods providing information about its behavior.

Description of the Agent and the Environment

An intelligent robotic agent is more than just a program. It is a complex system that interacts with an environment through percepts and commands. We use this model to describe the agent, the environment and their interactions.

Declaration of the System Components

Fundamentally our system consists of two parts: an agent and an environment as described in [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]. These two components are absolutely independent, an agent can run in different environments and an environment can be the home of different agents. Therefore our first step is to state which agent should run in which environment. These declarations are principally used to declare state variables and constants (see section 3.2).

Figure 8 shows the parts we have to specify and how this information is used in global variables. Our agent consists of a body, an architecture and a program. The program is a control procedure that is called when the agent is given the command to run. The body describes physical properties of the agent like its dimensions. The architecture provides the connection to the environment, it describes which features the agent can receive as a percept and what kind of command can be given. The environment the agent acts in has certain properties that remain unchanged over time. To summarize the information given by the agent and the environment we have three kinds of information, which is then provided by the global variables described in section 3.2: (1) a constant world model, (2) a belief state changing over time, and (3) a command.

Running the System

Now that we have declared an agent and an environment, we can run the agent. To do this, we call the function run-agent, which calls a method boot and starts a process update, both depending on the agent-architecture and the environment, and starts an RPL process that runs the agent-program. After initialization by the boot method agent and environment don't interact directly. The communication is done by the process update that gives the command in the controllable state variables to the environment and receives the percept, which it writes to the observable state variables. The state variables are set and read by a different process called RPL process which is running the agent program (figure 9). When the agent has finished its job or when we want to stop the agent from the outside, the function kill-agent is called to stop the RPL and update processes and to call a method shutdown that specializes over the architecture and the environment.

Environment

The Agilo Controller

Using the concepts described in the previous sections we have implemented a very simple controller for our soccer robots. The controller consists of two processes: a monitoring and a controlling process. For this purpose the RPL construct with-policy can be used very effectively as shown in figure 10. The action selection is now concentrated in one loop, whereas the failure testing is done outside.

Of course, this is a very simple controller that has to be enhanced. We are planning to use a belief-desire-intention architecture to make sophisticated decisions (see also section 6). We are developing RPL-II, the next generation of the robot control and plan language RPL. RPL-II supports the specification of high performance robot control programs by combining the expressiveness of RPL with respect to behavior specifications with advanced concepts that enable AI based control mechanisms to better reason about and manipulate control programs during their execution. The extensions we have realized so far include the support of specifying explicit models of the physical systems to be controlled and object-oriented modeling of control tasks and routines. In two companion papers we have described extensions for the explicit representation of learning tasks in experience-based learning [START_REF] Beetz | Rpl-learn: Extending an autonomous robot control language to perform experience-based learning[END_REF] and the tighter integration of programming and learning [START_REF] Kirsch | Programming robot controllers that learn[END_REF].

Still, these research results present only initial steps of the development of RPL-II, as a second generation AI-based robot control language. So let us briefly sketch the next steps on our research agenda: (1) comprehensive mechanisms for goal management, (2) improved physical system modeling, and (3) bootstrapping learning mechanisms for complex application tasks.

Comprehensive Goal Management. At the moment we only have the notion of lowlevel goals that are essentially constraints on state variables. So far RPL-II does not support goal selection that is consistent with the robot beliefs and other intentions of the robot. To support these goal management mechanisms we will add "desires" and "intentions" in addition to the current concept "goals" as first class objects in RPL-II and provide the respective reasoning mechanisms. This will give us the possibility of a much better action selection than the rule-based policy we are using now.

Deep models of state variables. While our current extensions make state variables explicit in the program code they still do not specify their physical meaning. We plan to provide such mechanisms by requiring programmers to specify the physical meaning in an explicit domain model formalized in a description logic. We believe that a concept taxonomy for a wide range can be provided and only small modifications for the individual application is needed. The slightly increased modeling effort will pay off immensely because using the domain model automated reasoning processes will be capable of solving much harder reasoning problems. For example, that all the conditions of a behavior trigger are observable or that two control routines will not interfere because the state variables they change are independent of each other.

Bootstrapping Learning Mechanisms. Finally, in RPL-II it will be possible to run partially specified control programs. The interpreter will then detect control tasks that the robot has no control routines for and acquire them by solving the associated learning tasks. This way a control program can complete itself or adapt itself to new environments and tasks by means of bootstrap learning.

Related Work

Model-based programming has been a major issue in several space exploration projects like Remote Agent [START_REF] Muscettola | Remote agent: To boldly go where no ai system has gone before[END_REF], Livingstone [START_REF] Williams | Livingstone: Onboard model-based configuration and health management[END_REF], the Mission Data System Project [START_REF] Volpe | Rover technology development and infusion for the 2009 mars science laboratory mission[END_REF], Reactive Model-based Programming Language [START_REF] Williams | Model-based programming of intelligent embedded systems and robotic space explorers[END_REF] and others [START_REF] Barrett | Domain compilation for embedded real-time planning[END_REF][START_REF] Ingham | A reactive model-based programming language for robotic space explorers[END_REF][START_REF] Knight | Extending the representational power of modelbased systems using generalized timelines[END_REF]. All of these projects represent the physical behavior of very complex systems in an explicit manner. This gives them the power to use lightweight reasoning techniques. The systems in these projects have to work very reliably. Vital parts of the physical systems are redundant, so that in the case of failure the system can be reconfigured. For this purpose the properties of the physical system parts have to be known by the controller. In our case reliability is not such an important issue. However, the environment our soccer robots have to deal with is much more dynamical. So we are interested in a robot that can adapt its control program to changing situations in its environment.

Conclusions

In this paper we introduce model-based concepts for the programming of robot controllers. The representation of state knowledge is done by state variables that are known throughout the system. Tightly coupled to the state variables is the representation of low-level goals. Those goals are achieved by control procedures arranged in two hierarchies: an object hierarchy that exploits inheritance mechanisms and a calling hierarchy including control tasks and control routines.

These concepts enable us to describe the robot and its environment declaratively. Using the robot control language RPL we can build a highly structured control program, where failure handling and action selection are separated.

On this basis we plan to include learning mechanisms as well as lightweight reasoning techniques. We still need to implement higher-level concepts like a belief-desireintention architecture or logic representations to facilitate reasoning in the controller.

Fig. 1 .

 1 Fig. 1. Chaining of actions.

Fig. 2 .

 2 Fig. 2. Code extract of our old AGILO controller.

Fig. 3 .

 3 Fig. 3. Some RPL control structures and their usage.

Fig. 5 .

 5 Fig. 5. Class hierarchy of procedures.

Fig. 6 .

 6 Fig. 6. Typical calling pattern of control tasks and control routines

Fig. 7 .

 7 Fig. 7. Method execute for class control task

Fig. 9 .

 9 Fig. 9. The system at work.

Fig. 10 .

 10 Fig. 10. Controller of our soccer robots 6 Research Agenda for RPL-II

  Class hierarchy of globally known variables.

			global value
			name
		state variable fluent	constant
	recording state	derived state variable
	variable		elements
	history		combination function
	observable state variable goal	controllable state variable
	Fig. 4.

Key Concepts of RPL-IIAfter we have given a summary of the necessity of building a model-based, objectoriented system in section 2, we now have a closer look at the concepts we want to employ. These concepts are


Freek Stulp

Alexandra Kirsch

Suat Gedikli

Michael Beetz

Michael Beetz Agilo

AGILO RoboCuppers 2004

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

System Overview

The AGILO RoboCup team is the primary platform for our research on the semiautomatic acquisition of visuo-motoric plans. It is realized using inexpensive, off the shelf, easily extendible hardware components and a standard software environment.

The control system of an autonomous soccer robot consists of a probabilistic game state estimator and a situated action selection module [START_REF] Beetz | The AGILO Autonomous Robot Soccer Team: Computational Principles, Experiences, and Perspectives[END_REF][START_REF] Beetz | The AGILO 2001 robot soccer team: Experience-based learning and probabilistic reasoning in autonomous robot control[END_REF]. The game state estimator computes the robot's belief state with respect to the current game situation [START_REF] Schmitt | Cooperative probabilistic state estimation for vision-based autonomous mobile robots[END_REF][START_REF] Schmitt | Designing Probabilistic State Estimators for Autonomous Robot Control[END_REF]. The action selection module selects actions according to specified goals as well as learned experiences. Automatic learning techniques made it possible to develop fast and skillful routines for approaching the ball, assigning roles, and performing coordinated plays [START_REF] Buck | Multi Robot Path Planning for Dynamic Environments: A Case Study[END_REF][START_REF] Beetz | Rpl-learn: Extending an autonomous robot control language to perform experience-based learning[END_REF].

The control program and the software development environment of the AGILO RoboCuppers 2004 advance the computational mechanisms of the earlier versions of the system in several important ways: 1. For the first time our probabilistic state estimation routines will employ learned observation and environment models and active state estimation routines. 2. The action selection is rationally reconstructed and completely re-implemented using ROLL (RObot Learning Language). Using ROLL, learning and control tasks are stated explicitly as part of the code.

The control system employs model-based transformational learning and planning

mechanisms in order to improve the system performance. 4. Finally, we have substantially extended the development environment for programming the control system. These extensions include a system for recording ground truth data and a software workbench for empirically analyzing robot behavior and perception.

Hardware Platform

The AGILO RoboCup team is realized using inexpensive, off-the-shelf, easily extendible hardware components and a standard software environment. The team consists of four customized Pioneer I robots (1); one of which is depicted in figure 1. The robot uses the original Pioneer I controller-board (2) and differential drive (3). For ball handling the robot has a passive ball guide rail (4) and a spring-based kicking device [START_REF] Beetz | Motion and episode models (simulated) football games: Acquisition, representation, and use[END_REF].

The only sensor apart from the odometry is a fixed, forward-facing color CCD Firewire camera with a lens opening angle of of 90 [START_REF] Beetz | Autonomous robot controllers capable of acquiring repertoires of complex skills[END_REF]. All computation is done on a standard 900 Mhz laptop with Linux operating system [START_REF] Belker | Learning action models for the improved execution of navigation plans[END_REF]. The robot uses a wireless Wireless LAN device (8) for communication with teammates.

CCD Camera ( 6)

Kicker (5) Differential Drive (3)
Wireless LAN ( 8)

Pioneer I Base (1)
Laptop, 900MHz ( 7)

Pioneer I Board (2)
Ball guide rail (4) Our hardware is somewhat Spartanic. Our off-the-shelf forward facing camera with 90 field of view has a very restricted view as compared to the omni-directional vision system and laser range finders that most RoboCup mid-size teams use. We also use a differential drive instead of the much more dextrous holonomous drives. Whereas this hardware gives us a substantial disadvantage against teams which use one or more of the above-mentioned components, it also confronts us with challenging research problems.

Vision-based, Cooperative Game State Estimation

The game state estimators of the AGILO robots maintain a belief state that contains the respective robot's belief about the current game situation. The belief state includes the estimated positions and orientations of the robot itself, its team mates, the ball, and the opponent robots and provides the information that is necessary for selecting the appropriate actions. Employing sophisticated probabilistic reasoning techniques and exploiting the cooperation between team mates, the robot can estimate complex game states reliably and accurately despite incomplete and inaccurate state information.

The state estimation system [START_REF] Schmitt | Cooperative probabilistic state estimation for vision-based autonomous mobile robots[END_REF][START_REF] Schmitt | Designing Probabilistic State Estimators for Autonomous Robot Control[END_REF] consists of the perception subsystem, the state estimator itself, and the belief state. The perception subsystem itself consists of a camera system with several feature detectors and a communication link that enables the robot to receive information from other robots. The belief state contains a position estimate for each dynamic task-relevant object. The estimated positions are also associated with a measure of accuracy, a covariance matrix. The state estimation subsystem consists of three interacting estimators: (1) the self localization system [START_REF] Hanek | Vision-Based Localization and Data Fusion in a System of Cooperating Mobile Robots[END_REF], (2) the ball estimator [START_REF] Hanek | Towards RoboCup without Color Labeling[END_REF][START_REF] Hanek | Towards RoboCup without color labeling[END_REF], and (3) the opponents estimator. State estimation is an iterative process where each iteration is triggered by the arrival of a new piece of evidence, a captured image or a state estimate broadcasted by another robot. Detailed information about the computer vision and probabilistic state estimation techniques can be found in [START_REF] Schmitt | Designing Probabilistic State Estimators for Autonomous Robot Control[END_REF].

The game state estimator that will be employed by the AGILO RoboCuppers 2004 control systems features several substantial improvements and novel capabilities. For the first time we employ probabilistic observation models that are learned from ground truth data. Second, the robots will be more cognizant about the properties of the belief state, whether their self-localization is inaccurate or ambiguous, whether distinctive landmarks are in view, etc. Inferring these properties of belief states will result in more useful information for robot control and better performance of cooperative state estimation. The third extension will be novel methods for active state estimation. Here, the information about the belief states are used for selecting actions that reduce the entropy of the belief state along different dimensions. For example, if the situation allows for the localization of a lost robot by looking at this robot, the state estimation proposes that the other two robots face the lost robot in order to reinitialize the lost robot's self localization. Other active state estimation routines will intelligently search for the ball, etc.

Our medium term goals in state estimation that we will tackle after this year's competition are methods for perceiving and estimating game situations rather than belief states with accurate robot positions. An example of such a situation is an opponent robot in ball possession directly threatening our goal or an open area in front of the opponents' goal that is appropriate for goal shots. We believe that the perception of such system will provide better information to the action selection and will be more robust to compute because lower data accuracy is required.

Another direction of further research is to add capabilities for partial state estimation. Instead of relying on global position estimates, the robot system should be capable of acting based on partial state estimation such as only the ball is seen directly in front of me, etc. How to switch from action selection based on global state information to the one based on partial information and how to exploit partial state estimates as evidence for a global estimate are open questions on our research agenda.

The Robot Learning Language (ROLL)

Although learning techniques have become powerful and successful tools for the development and adaptation of robot control programs, a control task such as "win a soccer game in mid-size robot soccer" is far too complex to be solved as a monolithic learning task. Therefore the action selection component of the AGILO RoboCuppers employs a variety of smaller and diverse learned routines that solve, among other ones, the following reasoning tasks: 1. What happens if the voltage of the left motor is set to 2 volt? 2. Which control signal must be issued to reach the position (-2.0, 1.0) with an orienta-tion of 96 ? 3. How long will it take to get to the ball? 4. How promising is an attempt to dribble the ball into the goal in the current situation?

The action selection module of the AGILO RoboCuppers 2004 is a rational reconstruction and complete re-implementation of the action selection module used in earlier versions (see [START_REF] Buck | Reliable Multi Robot Coordination Using Minimal Communication and Neural Prediction[END_REF][START_REF] Beetz | AGILO RoboCuppers 2002: Applying Cooperative Game State Estimation Experience-based Learning, and Plan-based Control to Autonomous Robot Soccer[END_REF][START_REF] Buck | Multi Robot Path Planning for Dynamic Environments: A Case Study[END_REF]). In the earlier versions of the action selection subsystem the learning tasks were solved in isolation and only the shared object files of the learned routines became part of the system. This yielded a number of severe drawbacks that made the development and improvement of the system very tedious and fragile.

Thus in the hot phases of preparation for RoboCup competitions, the learning processes were not properly documented. So afterwards it was impossible to find out the parameterization of the learning algorithms or which experiences had been employed. Thus, the solutions of a learning problem was irreproducible. This caused tremendous waste of resources when hardware components in the robots were replaced. The previously learned routine could not be used any more, a new one had to be learned from scratch and the same difficulties had to be solved anew.

To avoid these problems, in the new version of the action selection module the control tasks and learning problems are stated explicitly and declaratively. This is possible because we have added new execution mechanisms to the interpreter of our robot control system that make learning problems executable. Providing declarative and explicit specifications of learning problems and making these specifications operational supports the rigorous design of learning mechanisms and their transparent integration into the robot control systems.

Let us introduce the key concepts of ROLL using our second task from above as an example, that is the task of reaching a given position and orientation as fast as possible. A vital concept in our system is the notion of "experience". Experiences are represented as first class objects and form the basis of a learning process. The first thing a robot has to do is to make "raw experiences". He achieves this by following certain guidelines provided by a "problem generator", how to explore the field. These raw experiences are then transformed into abstract experiences to make them suitable for learning. Furthermore the experiences are filtered in order to eliminate contradictory or undesired experiences.

In our example the raw experiences are composed of the x-and y-coordinates and the orientation angle with respect to the x-axis. As this representation is not suitable for learning. Therefore we chose an abstract experience representation containing the distance of the start and goal points and the turning angle of the robot with respect to the connection line of the two points. When two similar experiences exist, only the one is maintained where the robot reaches its goal faster.

The abstract experiences are now given to a learning algorithm that generates an executable function which can be integrated into the control system of the robot.

For the implementation of our learning constructs we extended the robot control language RPL. The whole system is constructed in an object oriented style, so that certain parts of a learning problem specification can be reused for other problems by exploiting inheritance mechanisms. Our approach has been described in more detail in [START_REF] Beetz | Autonomous robot controllers capable of acquiring repertoires of complex skills[END_REF] and [START_REF] Beetz | Rpl-learn: Extending an autonomous robot control language to perform experience-based learning[END_REF].

Because of the complexity of our problems we learn them in simulation. For this purpose we have a simulator [START_REF] Buck | M-ROSE: A Multi Robot Simulation Environment for Learning Cooperative Behavior[END_REF] that models the dynamic of the environment very accurately. Soon we are going to extend its functionality by adding models of our state estimation module (see section 3).

Using Models of Skills to Optimize Plans

The core of the action selection module is a set of skills common to the RoboCup domain. In our previous system, these skills were selected based on a hand-coded rulebased policy. We are converting these skill selection rules into more generic goal selection rules. Based on the current belief state ("ball in own goal area", "free path to goal"), a goal is chosen ("get ball out of own goal area", "score goal"). The robot then selects the appropriate skill(s) to achieve this goal. In order to do this we now use more complex models of our skills. They consist of procedural knowledge, declarative knowledge, and projection functions.

The procedural knowledge specifies how the skill should be executed. It can be hand-coded, a set of if-the-else rules, a state chart, learned through Reinforcement Learning, or any other method, as long as it provides a primitive action for each belief state. It is also known as the policy. In many approaches, a skill consists only of this component.

Declarative knowledge about skills consist of pre-and postconditions. In the action selection module we do not specify high-level goals such as "win the game", or "defend", but intermediate goals such as "get ball out of own goal area", "score goal". A skill that has this goal as its postcondition will be selected, as it can achieve this goal. If there is no such skill, a light-weight planning module constructs a plan that combines skills to achieve this goal ("go to ball", then "dribble ball into goal"), using the pre-and postconditions specified in the declaritive component of the skills. The plan is executed as long as the preconditions for the plan still hold.

Projection functions allow us to make predictions about what will happen if we execute a skill. For instance, how long it will take to execute the task given a initial and goal-state? What is the chance of succeeding? This kind of knowledge is acquired by extensively executing the skill in a simulator, and recording the results. Neural networks are used to learn the mapping from ¢¡ ¤£ ¥¡ ¤¦ ¨ § © § ¡ ¤£ ¥¡ ¤¦ ! #" %$ ¡ '& )( 0¦ . We have used this approach before [START_REF] Buck | Reliable Multi Robot Coordination Using Minimal Communication and Neural Prediction[END_REF], and it has been very successful in coordinating our robots, by letting every robot predict how long it will take it to get the ball. ROLL, described in section 4, automates this learning process.

This approach combines the benefits of planning and learning. Pre-and postconditions allows the programmer to express action selection constraints in a declarative and transparent way. A light-weight planner then generates a plan using these conditions. As valid plans must not always be optimal, we use learned projection functions of skills to optimize them. Combining planning and projection functions has been researched in the context of Reinforcement Learning [START_REF] Malcom | Using abstract models of behaviours to automatically generate reinforcement learning hierarchies[END_REF], and hall-way navigation [START_REF] Belker | Learning action models for the improved execution of navigation plans[END_REF], but as far as we know, not in the RoboCup domain.

Realizing an autonomous robot control system is a very peculiar programming task that differs enormously from programming tasks in other application domains. While in most programming tasks we aim at programs that compute the correct results or do the right thing, in robot control we aim at programs that produce the optimal perception driven behavior. This difference is so big because the behavior does not only depend on the control program but also on the perception capabilities, the physical dynamics of the robot, system parameterization and the assignment of computational resources to computational tasks. Thus the very same programs may exhibit very different behaviors even if the influencing conditions are varied slightly.

For example, in the AGILO RoboCuppers control system the behavior of the robots critically depends on how computational resources are assigned to state estimation tasks and the remaining tasks. Or a variation of the camera model might cause inaccuracies in self localization and thereby cause problems in the role assignment within the team. Such interactions cannot be found and understood by looking at the program code. Rather, we have to identify the control parameters of our system and the context conditions that system performance depends, build a causal model of system behavior, and then learn the parameters of the causal model from empirical studies.

For this year's competition we have extended the software development environment for the AGILO RoboCuppers in two important ways. First, we have developed a camera system consisting of two cameras mounted at the ceiling, a visual marker system that allows us to recognize the individual robots on the field, and a global state estimation routine for tracking the positions and orientations of the ball and each robot on the field. This system provides us with ground truth data about the physical behavior of each robot where the expected accuracy of position data is about two centimeter in the center and about 4-5 centimeters at the boarders of the playing field. In addition, we have substantially extended our on-board logging mechanisms that give use very detailed information about the beliefs of the robot and the evidence the beliefs are based on at any time instance during the game. This setup is a huge source of data for the empirical study of our system.

The second extension is new workbench for the empirical study of system and agent behavior in simulated robot soccer, mid-size robot soccer, and human soccer [START_REF] Beetz | Motion and episode models (simulated) football games: Acquisition, representation, and use[END_REF] This workbench consists of a relational database system that stores the empirical data, an interpreter for recognizing and classifying behaviors based on observable features, and for data mining and visualization of empirical findings.

Sharing Belief within a Mixed Team

Due to scientific as well as pragmatic reasons, there is a growing interest in the robotics field to join the efforts of different labs to form mixed teams of autonomous mobile robots. As most robots in the F2000 league are custom built, or at least customized commercial research platforms with unique configurations of actuator and sensor configurations, mixed teams from different laboratories are extremely heterogeneous. This makes the unification of the software of the different robots of a potential mixed team almost impossible without substantial rewriting of at least one of the team's software.

Together with the teams of the University of Ulm (Ulm Sparrows) and the Technical University of Graz (Mostly Harmless) we have designed and implemented a communication framework for sharing information within a team of extremely heterogeneous autonomous robots, allowing us to play interchangeably with the different robot platforms in a mixed team [START_REF] Utz | Sharing belief in teams of heterogeneous robots[END_REF].

The communication framework is hardware and software independent, and can extend existing software architectures in a transparent way. Major code rewrites are not necessary to use this framework. The team communication uses a message-based, type safe high-level communications protocol that is transfered by IP-multicast. The implementation uses the notify multicast module (NMC) of the Middleware for Robots (MIRO) framework [START_REF] Utz | Miro -middleware for mobile robot applications[END_REF]. MIRO is a CORBA based middleware architecture for autonomous mobile robots.

For cooperation between robots, the sharing of information about beliefs concerning the state estimation is initially sufficient for successful cooperation. At the moment we therefore communicate only an expressive belief state using this framework; explicit role assignment or coordination is not part of the communication.

Summary

In this paper we have given an overview of the AGILO RoboCuppers team. After having discussed the main research directions in section 1, the hardware platform was presented in section 2. In the next three sections on vision-based, cooperative game state estimation (3), the robot learning language (4), and using models of skills to optimize plans (5), we have explained how we aim to implement semi-autonomous acquisition of visuo-motoric skills. In section 6 we have briefly discussed our ground-truth system, and our workbench for the empirical study of system and agent behavior in simulated robot soccer, mid-size robot soccer, and human soccer. Our cooperation with two other universities to design and implement a communication framework that allows platform independent exchange of belief states, and therefore mixed team coordination, was presented in section 7.

Fig. 1 .

 1 Fig. 1. An AGILO soccer robot


Mathieu Bouet

Jérémie Leguay

Vania Conan

Cost-based placement of vDPI functions in NFV infrastructures

Keywords:

Network Functions Virtualization (NFV) is transforming how networks are operated and network services delivered. The network is more flexible and adaptable. In particular, virtual Deep Packet Inspection (vDPI) engines can be dynamically deployed as software on commodity servers within NFV infrastructures for incremental monitoring. For a network operator, deploying a set of vDPIs over the network is a matter of finding the appropriate placement that meets the traffic management and operational cost constraints (license fees, network efficiency or power consumption). In this paper, we formulate the vDPI placement problem as a cost minimization problem. We cast the problem as a multicommodity flow problem. We then propose a centrality-based greedy algorithm and assess its validity by comparing it with the ILP optimal solution on random networks.

Introduction

Deep Packet Inspection (DPI) is a technique that allows fine-grained real-time monitoring of flows and users activity in networks and IT systems. It consists in filtering network packets to examine the data part (and possibly also the header) of a packet flow, identifying traffic types, searching for protocol noncompliance, viruses, spam, intrusions, or any defined criteria. Originally implemented as hardware middleboxes to be installed in network infrastructures, DPI are evolving towards the Network Function Virtualization (NFV) paradigm : they are being virtualized and delivered as software bundles that can be deployed and used on demand and on commodity hardware platforms. This approach is strongly supported by Internet Services Providers at ETSI [C + 12] to build the so-called NFV infrastructures, which basically consist in cloud platforms that can host network functions running. These infrastructures are intended to be deployed at PoPs (Points-of-Presence) or local aggregation points in carrier networks.

With virtual DPI (vDPI) network operators are facing a new set of challenges. The key question they have to address is the issue of where to instantiate the vDPI functions in their network. For the operator this decision is the result of a compromise between several possibly conflicting goals : in some case all flows must be monitored, and the obvious choice is to deploy one vDPI on every node. However, to reduce the cost (computing power, license fees, network utilization or power consumption), it may be more efficient to deploy less vDPI instances and pay an additional cost for rerouting traffic through these nodes. In other cases monitoring a sample of flows should be sufficient, but here again one should decide how many vDPI instances should be deployed and on which nodes.

Very recently, Luizelli et al. [L + 15] have proposed a binary search heuristic to jointly place VNFs (Virtual Network Functions) and map service chains onto them without any ordering constraints. The objective is to minimize the number of VNFs while meeting end-to-end delay guarantees. Our contribution differs from this work in mainly two points : i) our formulation is cost-based to finely represent global resource usages, ii) we consider that the sequence of functions is known in advance, i.e. each flow has to be monitored by one vDPI, which gives a competitive advantage to graph based heuristics such as ours. Addis et al. [START_REF] Addis | Virtual network functions placement and routing optimization[END_REF] proposed an ILP model that considers the traffic compression induced by multimedia gateways or firewalls for the cost efficient placement of VNF chains. They apply linearization techniques to increase the execution speed of an ILP solver. We propose a heuristic, for vDPI, to cope with the intractability of such formulations.

In this paper, we provide a general formulation of the vDPI placement problem as viewed by the network operator. We define a cost function that evaluates the quality of any given placement of vDPI and corresponding routing of the flows. We then present a centrality-based greedy algorithm and assess its validity by comparing it with the ILP optimal solution on random graphs.

Problem description

The problem we address in this paper can be formulated as follows : for a given NFV infrastructure and a given traffic demand, find a vDPI engine deployment that minimizes the overall cost. This cost optimization problem is the result of a joint minimization between i) the cost of vDPI engines and ii) the cost of the overall network footprint induced by flow redirections through the vDPI engines, while integrating iii) different operational constraints. These costs are financial costs associated with deployed vDPI engines (e.g. license price, CPU utilization, energy consumption...) and the cost of network resources (e.g. total cost of network ownership, capacity of the network to absorb new traffic). Operational constraints may include management limits such as the maximum number of engines to be deployed, the maximum used bandwidth per link (to be able to absorb peaks) and the maximum unmonitored flows. In the rest of this work, we assume that a third-party software editor provides the operator a vDPI software with a licence-based cost model : the cost is function of the quantity of vDPI engines deployed on the NFV PoP.

There is a tradeoff between the two main objectives which are, on the one hand, minimizing the number of vDPI engines and, on the other, minimizing the network load. Indeed, all the flows have to go through at least one vDPI engine to be analyzed. When the number of vDPI engines is small the network paths tend to be elongated. Therefore, minimizing the number of engines increases the additional used bandwidth. On the contrary, minimizing the used bandwidth increases the number of vDPI engines to be deployed. This problem can be casted as a multi-commodity flow problem [START_REF] Even | On the complexity of timetable and multi-commodity flow problems[END_REF]. Its formulation has to be extended to have a vDPI probe monitoring each flow [START_REF] Bouet | Cost-based placement of vDPI functions in NFV infrastructures[END_REF] with the objective function is :

Minimize ∑ i∈V d pi i * ω d pi + ∑ (i, j)∈E, f ∈F f size * (x f i, j + y f j,i ) * ω bw (1)
where ω d pi is the cost of a vDPI, ω bw the cost for using a unit of bandwidth and f size the size of the flow f which goes through the sets of links x i, j and y i, j . The constraints are those of multi-commodity flow problem applied with an extension to support pseudoflows (a flow is decomposed into two pseudo-flows : one from the source to the vDPI and one from the vDPI to the destination).

A centrality-based greedy algorithm

Heuristic description

Our main objective is to minimize the number of sites upon which vDPI probes are activated. To identify key sites where vDPI should be placed, we base our approach on nodes' centrality. Several types of centrality have been proposed and studied in graph theory as indicators which identify the most important vertices within a graph. One of the most used centrality metric is the betweenness centrality, which corresponds to the number of shortest paths that pass through a node. A node with high betweenness centrality has a large influence on the transfer of items through the network, under the assumption that item transfers follow shortest paths. We propose a new centrality metric, which is derived from the betweenness centrality. It combines two graphs, the first one being in our case the network topology G n (V, E n ) and the second one the traffic matrix G t (V, E t ). Our centrality for node i, namely centrality i , is equal to total size of the flows in G t which have their shortest path going through i in G n . A node with such a high centrality carries a large amount of traffic and is thus a good candidate to deploy a vDPI.

The objective function to balance the two costs remains the same as Eq. 1. It corresponds to the sum of the cost of used network resources and the cost of vDPI licenses activated. The heuristic we propose consists in a greedy algorithm that, at each step, considers placing a new vDPI on the node that has the highest centrality until the global cost stops decreasing. It is described in Algorithm 1.

Cost-based placement of vDPI functions in NFV infrastructures

Algorithm 1 Pseudocode for the greedy placement algorithm. The network footprint is evaluated incrementally (initialization takes place before the first iteration). For each flow, its shortest path through the nearest vDPI is calculated taking into account the available resources. When this shortest path is found, the used resources are removed from the available resources and the next flow is considered. The total network footprint is equal to the sum of the used network resources. We adopt an iterative shortest path allocation of all the flows for computational efficiency reason. The computation of the network footprint relies on a stateful algorithm, keeping in memory the current flow allocation to speed up further computations. Indeed between one iteration and the next one, the list of selected vDPI engines only differs by the last element (since a vDPI engine is added at each iteration). Therefore, instead of recomputing all shortest paths through each vDPI probe for each flow, we just need to compute the shortest path through the last probe.

At all steps, if the fitness value, that is its total cost of a vDPI deployment, is higher than the one of the previous vDPI placement, the greedy algorithm terminates and returns the previous vDPI placement. Otherwise, the unallocated flows that traverse the new vDPI are considered as allocated. Their resources are removed from the available resources. The next iteration starts with an updated topology and a reduced quantity of unallocated flows. In addition to an increasing fitness value, the algorithm has two other termination conditions. It terminates when the highest centrality is equal to zero, which means that all the flows have been allocated to a vDPI, or when the new vDPI has already been chosen, which means that all nodes have a vDPI.

Complexity analysis

In Algorithm 1, steps (S1), (S2), (S3) et (S4) call the Dijkstra algorithm. More precisely, steps (S2) and (S3) call the evaluateNetworkFootprint() function, (see description in the previous section) whose complexity is O(n 3 ln(n)). Other calls (S1) and (S4) have a complexity of O(n 2 ln(n)) or less, and are experimentally negligible compared to evaluateNetworkFootprint(). If p is the probes count at the end of the execution, n the number of nodes in the graph and d the mean node degree, then, experimentally, with Erdos graphs (and d = 3) we have p = n/3. Therefore when all loops are combined we get a total complexity : C(n) = 50 * n 4 * log(n) operations / comparisons for our heuristic.

Evaluation

We have implemented the ILP with GLPK and the heuristic using the Java Universal Network/Graph Framework (JUNG).We generated random graphs with the Erdös-Rényi degree distribution.The mean node degree is between 2.5 and 3. With this value, the resulting graph contained a big connected component and smaller ones, which are then connected to the big one by random links. We considered a traffic matrix where a 10 Mbit/s demand is created in both directions for each pair of nodes. We, of course, acknowledge that it does not represent reality, but aims at capturing an average case. We used a fix cost of $10 per Mb/s for the additional used bandwidth.

Each point on Fig. 1 corresponds to 10 simulations. We can observe on Fig. 1a that the heuristic find roughly the same number of vDPIs. The ILP stops after 35 nodes because of lack of memory while the same data the heuristic took 5.253s with our implementation. On Fig. 1b, comparing the optimal and the heuristic, we can observe a very good fit in terms of cost. In most of the cases, the heuristic finds an optimal solution.

Conclusion

In this paper, we formulated the vDPI placement problem as a cost minimization problem, capturing the different constraints the operator is facing. We casted the problem as a multi-commodity flow problem. We then proposed a centrality-based greedy algorithm and assessed its validity and comparing it to the linear program. In future work, we aim at reducing its complexity and address online placement.

1:

  function GREEDY PLACEMENT (Topology graph : G(V, E), List of traffic flows : F) Compute nodes centralities in (G, F u ) (S1) 6: d pi ← the node with the highest centrality in (G, F u ) 7: while centrality d pi > 0 and d pi / ∈ DPI do if f itness(G, F u , DPI) < f it min then 11: f it min ← f itness(G, F u , DPI) from G the resources used by the flows in F u whose shortest path goes through d pi (S3) 16: Remove from F u the flows whose the shortest path goes through d pi (S4) 17: d pi ← the node with the highest centrality in (G, F u ) 18: end while 19: end function 20: return DPI

  (a) Number of vDPIs. (b) Total cost.

FIGURE 1 :

 1 FIGURE 1: Evaluation on random graphs with Erdos node degree distributions. Figures represent for a site opening costs of $2500 the number of vDPIs (left) and the costs (right).