Integration of Operator Learning, Planning and Execution
in a Heterogeneous Multi-Robot System
YAMADA Seiji and IWASAKI Ryouhei
CISS, IGSSE, Tokyo Institute of Technology
4259 Nagatsuta, Midori, Yokohama, 226-8502, JAPAN
yamada@ymd.dis.titech.ac.jp
Abstract
This paper describes a practical framework in which generation of operators, planning and an execution of a plan are
integrated for a heterogeneous multi-robot system. In ourframework, first we design literals to describe an environment. Next a teacher directly manipulates real mobile robots
to achieve a task in the environment, and a sequence of thepairs of sensed data and an executed action is obtained. By
analyzing the sequence, a system is able to automaticallygenerate an operator by constructing a precondition-list, an
add-list and a delete-list from them. Once the operators are
acquired, a system can apply a complete and sound planner
GraphPlan to generate a plan. The generated plan is executedby instance-based learning with a Nearest Neighbor method.
This execution of a plan utilizes a sequence of the pairs ofsensed data and an executed action as a set of instances. Thusa system integrates operator generation, planning and the execution of a plan. The feasibility of our framework is verified through experiments in which two heterogeneous mobile
robots cooperatively achieve a task.
1. Introduction
One of important technologies for bridging between
AI(Artificial Intelligence) and robotics is planning. In the AI
planning, operators describing robot actions are given in advance, and the automatic generation of an operator sequencewhich can transform an initial state to a goal state[3, 6]. An
obtained sequence of operators is called a plan. An environment in which a robot works is described with predicate calculus, and a problem consisting of an initial state and a goalstate is given. In this context of AI planning, planning is justto search for a plan, and most of the studies in AI planninghave been done on purpose of developing an efficient searchalgorithm. However, planning is essentially a sub-system of
a whole framework in which a robot recognizes an environment, describes the environment and operators, generates asequence of actions and executes it. Though searching for aplan is significant, automatic generation of operators recently
has been recognized as very important and difficult for a practical application of planning to robotics. Nevertheless few attempt has been done for generating operators in robotics andAI[8, 7].
A multi-robot system is also an important issue in the viewof engineering because many practical robotics systems are
consisting multiple robots. However most of the investigatedmulti-robot systems are homogeneous in the sense that all
the robots have identical sensors and actuators. Though such
systems are robust to breakdown of some robots, they haveno adaptation that individual robot plays a different role depending on its ability. In a real environment, a multi-robot
system inevitably becomes heterogeneous since no physicalrobots are completely identical and they are often different in
the function. Thus we need a framework for a heterogeneous
multi-robot system.
Hence we propose a practical framework in which generation of operators, planning and the execution of a plan are
integrated for a heterogeneous multi-robot system. In ourframework, first we design literals to describe a environment.
Next we actually manipulate a real mobile robot to achieve atask in the environment, and a sequence of the pairs of sensed
data and an executed action is obtained. By analyzing thesequence, a system is able to automatically generate an operator, and apply an efficient planner to generate a plan. The
generated plan is executed by instance-based fashion. As a result, a system integrates operator generation, planning and theexecution of plans. We verify the feasibility of our framework
through experiments in which two different types of mobile
robots cooperatively achieve a task.
Wang proposed a method to generate and refine operators using a machine learning approach[8]. A version spacemethod and a large number of training examples were utilized for operator generation. The experimental results supported that the approach is promising. Unfortunately the environment was symbolic, and no real environment in whicha physical robot actually works was dealt with. In contrast
with the study, we apply our framework to a real and physicalenvironment using real mobile robots.
Schmill, at. el [7] studied learning for classifying sensed
data into action classes using an efficient inductive learningalgorithm C4.5. They made experiments in a real environment using a physical mobile robot. However they did notpropose a concrete method to generate an operator in theirresearch. Our framework not only deals with a real environment but develops a method to generate operators.
2. System overview
We propose a framework in which a mobile robot is able tolearn necessary operators by user’s simple and direct teaching
to do planning and execute a plan. Fig. 1 shows the overview
of our system. It has three modes: a learning mode, a test

SystemEnvironment
sensordata

learn_mode
test_mode

plan_mode
movement

robot

Figure 1 System overview
Main

Vision Khepera

Gripper Khepera

als is called an environment model. For simplicity, we use
no variable for describing the literals. These primitive literals
are designed in advance, and an operator is automatically acquired through teaching. For example, P roximityF ront,
P roximityRight, LightBack are literals for an environment model. A snapshot of an environment model is calleda state. A planning problem is described with a pair of an
initial state and a goal state. An initial state means an initialenvironment model when a robot starts to work, and a goalstate means a final environment model which a robot should
approach.
3.2. Operator

Learned operators

Figure 2GUImode and a planning mode, and a user(teacher) can change
the modes anytime. Thus a user can teach a robot in a learning mode as monitoring its execution in a test mode. Also auser can teach a robot immediately when a robot fails planning in a planning mode. A user and a robot can cooperate interactively to generate and execute a plan. User-frendly
GUI(Fig. 2) is provided for a user to change modes and monitor various information on an operator and sensed data.
• A learning mode: A user directly teaches a robot, and arobot can learn executable operators by the teaching. In
the teaching, a user directly manipulates a mobile robot
through GUI to perform a given task like remote control. Furthermore a system is able to delete and teachagain an operator which failed to be executed in a testmode.
• A test mode: A user checks whether a generated operator in a learning mode can be executable or not.
• A planning mode: Using generated operators, a given
initial state and goal state, a system generates a plan.
3. Environment model, operator and planning
3.1. Environment modelIn our system, an environment is described a conjunctionof literals obtained from sensed data. Thus this set of liter-

An operator is basically described with a precondition-list,
an add-list and a delete-list. The precondition-list means a setof literals which are necessary to execute the operator. The
add-list means a set of literals which become true after the
execution of the operator, and the delete-list stands for literals
are deleted from the state after the operator execution. Thus
an operator application to an environment model transforms astate. This is a popular description in traditional AI planninglike STRIPS[3, 6].
Additionally we introduce an instance set for executing an
operator using a robot in a real environment. The instanceset consists of pairs of sensed data and an executed action byteaching. As mentioned later, a Nearest Neighbor method is
utilized to execute an operator, thus an instance set is necessary. Examples of an operator and an instance set are shownin Fig. 3.
3.3. Planning
As mentioned before, planning is generation of an operator sequence to transform an initial state to a goal state. Since
development of an efficient planning algorithm is not a purpose of this study, we employ Graphplan[1], one of complete
and the most efficient planners. Graphplan describes a plan
as a directed graph having causality among operators, and theplanning is dealt with as manipulation of the graph. Using
Graphplan, a system is able to generate an adequate plan efficiently.
We explained the overview of our framework above. In thefollowing sections, we describe how to generate and execute
an operator in more detail.
4. Automatic generation of operators
Fig. 3 shows learning of operators by direct teaching by
a human teacher. He/she teaches a mobile robot by directly
manipulating it like remote control. Using GUI(Fig. 2), ateacher can easily control a mobile robot, and monitors the
behavior, sensed data and literals.

A teaching finish state
ProximityFront
RedAroundgo_straightgo_leftgo_straightgo_left
turn_left
turn_left
A teaching start state

Teaching
actions

ProximityLeft

Instance set(operator ApproachRed(params)(precond-list(ProximityLeft))(add-list(ProximityFront)(VKRedAround))(delete-list(del ProximityLeft)))

ActionSensed data
turn_left 221,103,100,...
turn_left 210,122,131,...
go_left
523,442,122,...
go_straight333,235,231,...
go_left
544,432,135,...

...

Operator

Figure 3 An operator and the learning
4.1. Checking literals
Since GUI shows a current state, a teacher can recognize
literals which are true in an environment through it. However,checking whether a literal is true or false from sensed data
is difficult because we hardly design a stable and accurate
function to classify the literal’s value with sensed data.
Thus we obtain instances consisting of sensed data andliterals’ values, and utilize a 1-Nearest Neighbor method[2]for determining literal value. Also CNN(Condensed Nearest Neighbor rule)[5] and RNN(Reduced Nearest Neighborrule)[4] are applied to reduce instances. Furthermore significant attributes are given to a system as background knowledge. This instance-based approach is experimentally foundbetter than designing a classification function.
4.2. Generating an operator
At the beginning of teaching, the state is stored as a teaching start state. A teacher selects next action on a current state,tell it to a robot, and the robot executes it in a real environ-ment. This direct teaching is repeated until a teacher stops
it. A teacher monitors literals and stops teaching when an execution of a single operator finishes. When a teacher stops
teaching, the state is stored as a teaching finish state. The
teaching start state and the teaching finish state are inputs foran operator generation procedure.
During teaching, a robot constantly stores the pairs ofsensed data and an executed action as an instance set for
instance-based operator execution. These pairs are utilized
to execute the learned operator when a plan including it isexecuted.
An operator is automatically generated using the following procedure in a learning mode. The inputs are a teaching
start state and a teaching finish state, and the output is an operator.
1. A teacher describes a name of an operator.
2. A system generates a precondition-list including all the
literals in a teaching start state.
3. A user teaches a robot by directly operating it step bystep through GUI. During this teaching, a system storesthe pairs of sensed data and an executed action as an
instance set for later instance-base operator execution.
At last, a user stops teaching.
4. By comparing a teaching finish state Sf with aprecondition-list P , the add-list and the delete-list are
generated. The add-list is obtained by P ∩ S f and thedelete-list is generated from P ∩ S f .
5. An execution of an operator
As well as operator generation has not been studied actively, a method to execute a plan using a physical robot has
not been developed so much. In our framework, we propose
an instance-based operator execution of a plan. The procedure is described like the following.
1. By observing an environment, an add-list and a deletelist are checked. If all the literals in the add-list are true
and no literal in the delete-list is true, the execution of
the operator is finish.
2. A robot selects an action using a 1-Nearest Neighbormethod[2] with the operator’s instance set. It comparescurrent sensed data with data in the instances, and themost similar instance is determined. The action of theselected instance is executed by a robot.
3. Go to 1.
A k-Nearest Neighbor method outperforms a 1-Nearest
Neighbor method in the case that a large number of instances
are available. In this instance-based operator execution, a few
instances are obtained in a learning mode because an operator has a relative small number of instances. Thus, due to thecost of a k-Nearest Neighbor method for selecting the best k
instances, we employed a 1-Nearest Neighbor method in our
research.

55mm

2

3

1

4

0

5

32mm

Goal (bule region)

DC motor
Infraredproximity sensor
7
6

Figure 4 Khepera.

Figure 5 Sensor positions.

Objext (red cylinder)
VisionKhepera
with a light
GripperKhepera
with a green cylinder

Figure 7 Experimental environment.

(a) VisionKhepera(b) GripperKhepera

Figure 6 Heterogeneous multiple robots.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

6. Experiments
In this section, we describe experiments for investigating
the feasibility of our framework in a real environment where
heterogeneous mobile robots work.
6.1. Heterogeneous multiple robots
We employ a small mobile robot Khepera(Fig. 4) which isvery popular in AI and robotics researches. Khepera has eightIR proximity sensors and light sensors at the same positions
as shown in Fig. 5. Khepera can recognize an object only
within 20mm around using an IR proximity sensor, and a far
light using a light sensor.
Two types of Khepera mobile robots(Fig. 6) are used forexperiments. The VK(VisionKhepera) has a color CCD camera (270,000 pixels) and a light on the top like Fig. 6(a). VK
recognizes the direction of a far colored object, however it can
not grasp the object because of no gripper. In contrast with
VK, the GK(GripperKhepera)(Fig. 6(b)) can grip an object
with its gripper, and can not recognize a far colored object
because of no CCD camera. GK has a green cylinder on the
top which can be recognized by VK. Also since VK has alight, GK can recognize its direction with the light sensors.
In the sense that these mobile robots have different sensors
and actuators, a multi-robot system consisting of them is heterogeneous.

VisionKhepera

GripperKhepera

ObjectGoal

Figure 8 Cooperative object gathering.
6.2. Experimental environment
The two robots work in an environment shown in Fig. 7.
The environment is a 72cm×72cm square area surroundedwith white walls. There is a red cylindrical object and a blue
goal region on the wall, which VK can recognize their directions and GK can not do so. Since the object, the goal region
and GK have different colors, VK is able to distinguish them.
In this environment, even a simple task like moving a red
object to a goal needs cooperation between the two mobile
robots. Hence this environment is valid for investigating ourframework.

6.3. Cooperative task
We verify the validity of our framework with a cooperative task in a heterogeneous multi-robot system. The task isthat two mobile robot move a red object to a blue goal region. A single robot VK or GK can not achieve this task
because VK can not grasp the object and GK can not findit. Thus one of solutions to this task is shown in Fig. 8. We
define the following operators for the solution, however theprecondition-list, the add-lists and the delete-lists are learned
automatically. In the following operators, (i)–(j) means theoperator corresponds an action from (i) to (j) in Fig. 8.
• ApproachRed: VK rotates and approaches a red object.
(1)–(2)• FindGripperKhepera: VK does wall-following aroundthe red object until GK becomes visible. (2)–(3)• ApprochVisionKhepera: GK approaches VK by recognizing its light. (3)–(4)• ApprochBlue: VK approaches the blue goal and rotates
there until it finds the GK. (4)–(5)• GripObject: GK approaches the red object and picks itup. (5)–(7)• ApproachGoal: GK approaches the blue goal by recognizing the light of VK. (7)–(8)• ReleaseObject: GK puts down the red object in front of
VK. (8)–(9)The literals are carefully designed by a human designer.
Table 1 shows the name and interpretation of the literals.
We consider the literals are sufficient, even not necessary.
Also actions which the robots can execute are defined. Actions go left, go straight, go right, turn left, wait, turn right,back} are defined for VK. For GK, actions {grip object, release object are defined in addition to the VK’s actions.
To perform the task, we give our system a problem: an
initial state {VKProximityLeft, GKLightFront} and a goalstate {VKProximityBack, VKRedAround, GKLightFront,
GKProximityFront}. This problem means that robots move
an red object to a blue goal region.
6.4. Experimental results
In order to achieve this task, we directly manipulated VK
and GK in a learning mode for generating the operators mentioned above, and a system acquired the operators successfully. Next a system generated a plan to solve the problem using the learned operators and Graphplan in a planning mode.
Finally the two mobile robots executed the plan in a real environment, and the goal state was satisfied.
Fig. 9 shows a generated plan. In this figure, the descriptions of learned operators are indicated. Fig. 10 shows the
trajectories of VK and GK in a real environment. We verified
that they worked based on the plan and successfully achieved
the goal state.

Literal name
VKProximityFront
GKProximityFront
VKProximityBack
GKProximityBack
VKProximityLeft
GKProximityLeft
VKProximityRight
GKProximityRight
VKLightFront
GKLightFront
VKLightBack
GKLightBack
VKLightLeft
GKLightLeft
VKLightRight
GKLightRight
VKRedAround
GKGrippedObject
VKGreenAround
VKBlueAround

Interpretation
An object in the front of VK
An object in the front of GK
An object at the back of VK
An object at the back of GK
An object on the left of VK
An object on the left of GK
An object on the right of VK
An object on the right of GK
A light in the front of VK
A light in the front of GK
A light at the back of VK
A light at the back of GK
A light on the left of VK
A light on the left of GK
A light on the right of VK
A light on the right of GK
A red object in the front of VK
GK grasps an object.
A green object in the front of VK
A blue object in the front of VK

Table 1 Literals used in the experiments.
7. Discussions
7.1. Design and check of literals
In a current system, we need to carefully design sufficient literals for achieving a given task as mentioned in 6.3.
This design of literals becomes very hard for a human designer as a task gets more complex. Though an full-automatic
method for designing literals is difficult, we need to develop
a semi-automatic approach in which a system and a designer
defines sufficient literals interactively. We consider unsupervised learning is applicable to generate candidates of literals.
7.2. Segmentation of operators
The segmentation of operators from a sequence of actions
is done by a human teacher. He/she explicitly divides thesequence into operators by pointing out a teaching teaching
start and a teaching finish state. However a system should
segment a whole action sequence consisting of necessary operators to achieve a task into adequate sub-sequences. Whentasks to be performed are given, the segmentation is realized
so that the obtained operators can be necessary and sufficientto achieve all the tasks. Since this segmentation needs combinational search, we have a plan to employ an evolutionary
computation approach.
8. Conclusion
We proposed a practical framework in which the generation of operators, planning and the execution of a plan were
integrated for a heterogeneous multi-robot system. In ourframework, first we designed literals to describe a environment, and directly manipulated real mobile robots to achieve

Initial state(VKProximityLeft)(GKLightFront)(VKProximityFront)(VKProximityRight)(VKGreenAround)(GKLightFront)(GKProximityFront)(operator ApproachRed(params)(precond-list(VKProximityLeft)(GKLightFront))(add-list(VKProximityFront)(VKRedAround))(delete-list(VKProximityLeft)))(operator ApproachBlue(params)(precond-list(VKProximityFront)(VKProximityRight)(VKGreenAround)(GKLightFront)(GKProximityFront))(add-list(VKProximityBack)(VKRedAround))(delete-list(VKProximityFront)(VKProximityRight)(GKProximityFront)))(VKProximityFront)(VKRedAround)(GKLightFront)(operator FindGreen(params)(precond-list(VKProximityFront)(VKRedAround)(GKLightFront))(add-list(VKProximityRight)(VKGreenAround))(delete-list(VKProximityFront)(VKRedAround)))(VKProximityBack)(VKRedAround)(VKGreenAround)(GKLightFront)(VKProximityRight)(VKGreenAround)(GKLightFront)(operator ApproachLight(params)(precond-list(VKProximityRight)(VKGreenAround)(GKLightFront))(add-list(VKProximityFront)(GKProximityFront))(delete-list ))(operator GripObject(params)(precond-list(VKProximityBack)(VKRedAround)(VKGreenAround)(GKLightFront))(add-list(GKGripObject))(delete-list(VKRedAround)))(operator ApproachGoal(params)(precond-list(VKProximityBack)(VKGreenAround)(GKLightFront)(GKGripObject))(add-list(VKProximityFront)(GKProximityFront))(delete-list ))(VKProximityFront)(VKProximityBack)(VKGreenAround)(GKLightFront)(GKProximityFront)(GKGripObject)

Figure 10 Execution of a plan in a real environment.
(operator ReleaseObject(params)(preconds(VKProximityFront)(VKProximityBack)(VKGreenAround)(GKLightFront)(GKProximityFront)(GKGripObject))(add-list(VKRedAround))(delete-list(VKProximityFront)(VKGreenAround)(GKGripObject)))(VKProximityBack)(VKRedAround)(GKLightFront)(GKProximityFront)

Goal state(VKProximityBack)(VKGreenAround)(GKLightFront)(GKGripObject)

Operator
State

Figure 9 Generated plan.
a task in an environment. As a result, the initial state, thefinish state and a sequence of the pairs of sensed data and an
executed action were obtained. Using the two states, a system can generate an operator by constructing a preconditionlist, an add-list and a delete-list. Once the operators wereacquired, a system can apply a complete and sound planner to generate a plan. The generated plan was executed byinstance-based operator execution with a 1-Nearest Neighbormethod using the pair of sensed data and an executed action. Thus operator generation, planning and the executionof a plan were integrated in our framework. The feasibilityof our framework was verified through experiments in whichheterogeneous mobile robots cooperatively achieved a task.

References[1] A. Blum and M. Furst. Fast planning through planninggraph analysis. Artificial Intelligence, 90:281–300, 1997.
[2] B. V. Dasarathy. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society
Press, 1991.
[3] R. E. Fikes and N. J. Nilsson. STRIPS: A new approachto the application of theorem proving to problem solving.
Artificial Intelligence, 2:189–208, 1971.
[4] G. W. Gates. The reduced nearest neighbor rule. IEEE
Transactions on Information Theory, IT-18(3):431–433,
1972.
[5] P. E. Hart. The condensed nearest neighbor rule. IEEE
Transactions on Information Theory, IT-14(3):515–516,
1968.
[6] S. Russell and P. Norvig. Artificial Intelligence –A Modern Approach–. Prentice-Hall, 1995.
[7] M. D. Schmill, M. T. Rosenstein, P. R. Cohen, and P. Utgoff. Learning what is relevant to the effects of actions
for a mobile robot. In Proceedings of the Second International Conference on Autonomous Agent, pages 247–253,
1998.
[8] X. Wang. Learning by observation and practice: An incremental approach for planning operator acquisition. In
Proceedings of the Twelfth International Conference on
Machine Learning, pages 549–557, 1995.