Observation strategy for decision making based on information
criterion
Noriaki Mitsunaga

Minoru Asada

Dept. of Adaptive Machine Systems
Osaka University
Suita, Osaka, 565-0871, Japan

mitchy@er.ams.eng.osaka-u.ac.jp asada@ams.eng.osaka-u.ac.jp
Abstract
Self localization seems necessary for mobile robot
navigation. The conventional method such as geometric reconstruction from landmark observations is generally time-consuming and prone to errors. This paper proposes a method which constructs a decision tree
and prediction trees of the landmark appearance thatenable a mobile robot with a limited visual angle toobserve efficiently and make decisions without global
positioning in the environment. By constructing thesetrees based on information criterion, the robot can accomplish the given task efficiently. The validity of themethod is shown with a four legged robot.

1

Introduction

When it makes a decision, a mobile robot highly depends on its own location. For self-localization, methods such as dead reckoning and global positioning bygeometric reconstruction from image data are commonly used. However, it seems difficult for a legged
robot to use dead reckoning since the moving distanceon the walking plane is less accurate than that of awheeled robot. For the latter, geometric reconstruction often highly depends on accurate motion information. Such information may include drastic errors in
the case of legged robots due to causes such as slipping.
Furthermore, it takes a lot of time not just for geometric reconstruction but also for observation to capture
the image surrounding the robot in order to make geometric reconstruction stable and accurate. Humanbeings do not seem to take such a strategy to localize
themselves. Rather, they use the minimum necessary
information for their decision making when they do
not have enough resources (time, etc.).

Moon et al. [3, 2] have proposed a view point planning method to move efficiently by reducing the frequent observation for self-localization mostly based ondead reckoning. To apply their method, the map andthe route to the goal should be given in advance.
Burgard et al. [1] have proposed an active localization method by Markov localization using occupancy
grids as a world model representation. To apply their
method, the map of the environment and the deadreckoning model need to be prepared. Also calculation and memorization costs for occupancy grids arevery high. These methods depend on geometric reconstruction.
Tani et al. [6] have experimented with the task ofwatching two visual targets with a limited view angle
camera. The robot switched the visual attention depending on prediction accuracy. Since the robot action(wall following) is fixed, the issue can be regarded asa view prediction problem on a route which is almost
fixed.
In this paper, we propose a method for a robot,
which has a limited view angle camera with panningfacility, to make a decision by efficient observation
without explicitly localizing itself. With a limited view
camera, a robot can widen the angle by panning, but
it takes time. Efficient observation is done by a decision tree and prediction trees constructed based on
the information criterion. The basic idea of our observation strategy is not for self localization but for
decision making, that is, to minimize observation aslong as decision making is possible. By constructing
a decision tree, one can know which landmark to observe first. Similarly by making and using prediction
trees with information criterion, one can reduce thetime for observation through decision making.

2

The method

2.1

Assumptions

actionx
Landmark A

LandmarkA

We assume that the robot can make a decision for
the given task at any position by panning its camera head. Before making the decision and prediction
trees, sufficient example data are necessary. We used
a teaching method to collect such data.

2.2

2

pk =

nk
,
n

(1)

where nk denotes the number of taken action k. Therefore, the information I0 for the action probability isgiven byX
I0 = −
pk log2 pk .
(2)kNext, calculate the occurrence probabilities of actions
after each appearance of the landmark was known. We
denote the number of times action k was taken as nijk
when the landmark i is observed at the quantized direction j. Then, the occurrence probability becomes,nijk
pijk = P.
k nijk(3)

Next, calculate the expected information after one ofthese landmarks is found, as follows:X© P nijk XªkP P
Ii = −(pijk log2 pijk ) . (4)jk nijkjkThe smaller Ii is, the smaller the uncertainty after theobservation is. We put the landmarks into the tree indecreasing order of uncertainty after its observation.
This information criterion is same as ID3 [4]. For the
training data which take different actions for the same
situation, we add a leaf for each action and record theprobability that it was taken.

3

Landmark B
Take 1
action x

2
z

3
z

y

(a) action decision tree

Making decision and prediction trees

Suppose we have m landmarks and q kinds of actions. Each appearance of the landmark is quantized
into r kinds of viewing categories including a nonvisible situation. A training datum consists of a setof the appearance of the landmarks at the current position and the action to accomplish the task, and wehave n training data. During the training period, therobot pans its camera head from the left-most angle to
the right most one, and observes as many landmarks
as possible.
First, calculate the occurrence probabilities of actions pk (k = 1, ..., q) as:

1

1

y

2

Landmark B
1

Landmark B
1
2

Landmark C
2
2

Landmark C
3 0.3
3
1

Landmark A
at t+10.7
3(b) landmark prediction tree

Figure 1: Examples of an action decision tree and a
prediction tree.
For example, suppose we have training data as shownin Table 1. Since px = 0.2, py = 0.4, and pz = 0.4,
I0 is 1.52. By calculating each pijk , we have expected
informations, IA = 0.551, IB = 0.8, and IC = 1.2.
So the ordering in the decision tree is landmark A, B,
and C, and the tree is shown in Fig.1(a). We calculate
the landmark appearance prediction trees in the samemanner.
Table 1: An example of teaching data.
Landmark A Landmark B Landmark C Action
1
1
1
x
2
1
1
y
3
2
1
y
1
3
1
z
1
2
2
z

2.3

Calculation of the probability distribution

Here, we denote the probability that the viewing
direction of the landmark i is j at time t as pLij (t) (i =1, ..., m, j = 1, ..., r), the probability that the action
k was taken at time t as pak (t) (k = 1, ..., q), and theprobability that the action k should be taken by thetraining data at t as p̂ak (t) (k = 1, ..., q).
Calculation of the probability distributions are as
follows. If currently the landmark i is observed in thequantized viewing direction J we assign the probabilL
ity 1.0 to pLiJ (t) and 0s to others (pij (t) = 0 (j 6= J)).
When the previous taken action was K, set paK (t−1) =1 and pak (t − 1) = 0 (k 6= K). The probabilities of thelandmarks, which are not currently observed, are predicted by the prediction trees using the probabilityadistributions pL
ij (t − 1) and pk (t − 1). We assign theTo calculate the action decision probability p̂ak (t),we use these probability distributions pL
ij (t), and follow the action decision tree in the same manner.

2.4

Figure 2: The SONY legged robot for RoboCup 99
SONY legged robot league.

Decision making

NW

3.1

Experiments
Task and Assumptions

The task is to push a ball into a goal based on thevisual information. We used a legged robot with alimited view angle for the RoboCup 99 SONY legged
robot league (Fig.2). In the field, there are 8 landmarks, that is, target goal (TG), own goal (OG), northwest pole (NW), north east pole (NE), center west pole
(CW), center east pole (CE), south west pole (SW),and south east pole (SE). All the landmarks and theball are distinguished by their colors. The view angle/ number of image pixels of the robot’s camera are

CE

1500

CW

1800
SW
2000

(a) Photo of the field.

3

NE

1500

In order to make a decision on which action to take,the robot calculates the p̂ak (t) as described above. If
one of the action probabilities is very high, it takesthat action. Otherwise, until one of them becomeshigh enough, it continues to try to observe the landmark whose probability distributions is flat in the order in which they were placed in the action decision
tree (information criterion). When the robot checks
the landmark, one may find a peak of the profile, andobservation of that direction may help.

TG

2800

a
L
L
pL
A1 (t) = px (t − 1)pA2 (t − 1)pB2 (t − 1) × 0.3,
a
L
L
L
pL
A2 (t) = px (t − 1)pA1 (t − 1)pB1 (t − 1)pC2 (t − 1),
a
L
L
L
pL
A3 (t) = px (t − 1)pA2 (t − 1)pB1 (t − 1)pC3 (t − 1)L+pax (t − 1)pL
A2 (t − 1)pB2 (t − 1) × 0.7. (5)about 53 degrees / 88 pixels in width, and about 41
degrees / 59 pixels in height. Each leg and the neckhave three degrees of freedom. We fixed the joint angles of the legs and the neck except for the pan joint
when it observes the landmarks and the ball to makeits decision. The robot can rotate the pan joint from-90 degrees to 90 degrees.

600

250

probability 1.0 to the quantized invisible direction and
0s to others if the landmark cannot be observed while
the robot looks around.
Following a landmark prediction tree from the root
to one of the leaves, one can obtain 1) the conditionof the appearances of the landmarks and the action attime (t − 1) which is given by logical product, and 2)
the consequence appearance of the landmark at time t.
In order to calculate the probability of reaching eachleaf, we change the logical product to an arithmetic
one and conditions to probabilities at time (t − 1).
We consider the summation of the probabilities of theleaves of the same appearance as the probability of theappearance at time t. For example, if the prediction
tree of landmark A is Fig.1(b), thenSE
OG(b) Size of the
field.

Figure 3: Experimental field (same as the one for
RoboCup SONY legged league). Cross marks and acircle indicate the initial positions of the robot and theball respectively for the first experiment.
The ball can be treated as a special landmark, whichis static if the robot does not push it while it canchange its position if the robot pushes it. Therefore,
the appearance of the ball can be predicted by its previous location in the image and the action of the robot.
Note that for the ball prediction tree we cannot useother landmarks because it may move in the field.
Each landmark’s appearance is quantized into eightcategories, that is, seven directions and one invisible
situation (Fig.4). The ball appearance was quantized
into eleven categories, that is, the product of five directions and two kinds of distances (near or far), andone invisible situation.
3

4

8

7

5

9

2
6

2
6

1

3

1

4

10

5

7

Table 2: Depth of the action and prediction trees (Experiment 1).
# of leaves min dep. mean dep. max dep.
action:
43
1
4.91
8
ball:
52
2
2
2
OG:
13
1
4.23
8
TG:
44
1
5.39
8
SE:
6
1
2
3
SW:
1
0
0
0
CE:
28
2
4.69
8
CW:
11
1
3.91
8
NE:
51
1
5.96
8
NW:
54
2
5.91
8

30degrees
near

far

Figure 4: Quantization for landmarks (left) and theball (right).

Since the training data may lack some
PN situations,the sum of the probability distribution i=1 pi mightPN
be less than one. To avoid this, we added (1− i=1 pi )/N
to each pi . N indicates the size of the distribution.
When it plays back the taught action based on thetrees, the robot looks all around to search landmarks
and the ball (if they are invisible) if the peak action
probability was below 0.6 .

3.2

Table 3: The order of information of trees (Experiment 1, ‘act’ means action, ‘1’ means root node).
1
2
3
4
5
6
7
8
action: ball TG NE NW CW CE OG SE
ball: ball act
OG: act NE TG NW CW CE OG SE
TG: TG
act NE NW CE OG CW SE
SE: act CE NE OG NW TG CW SE
SW:
CE: act NE TG CE NW CW OG SE
CW: TG
act NE NW CE CW OG SE
NE: NE
act NW TG CE CW OG SE
NW: act NE TG NW CE OG SE CW

Experiment 1

In the field (Fig.3), we experimented with the taskof guiding a ball into the goal. The ball was put infront of the goal (the circle before the target goal in
the figure) and the robot was placed at middle of the
field (one of three cross marks in the middle). As actions, we prepared three movements, forward, left forward and right forward for 4.8 seconds. The walking
was programmed by us and a motion for 4.8 seconds
corresponds to four walking periods. In 4.8 seconds,
the robot walks about 0.45[m] in forward movement
and at most places the appearance of the landmarks
changes due to one of the motions.
We trained the robot starting from one of three positions in the middle of the field. For each starting position, we trained five times and obtained eighty data
points to construct trees. We show the sizes (the number of leaves, minimum, mean, and maximum depth)of decision and prediction trees in Table 2. The orders
in the trees by the information criterion are shown in
Table 3.

Next, we show the examples of action sequencesusing these trees. From the starting position in thecenter of the field, the robot took the forward motions
four times. In this experiment, the ball and the target
goal were observed at every moment for decision making. The probability distributions of landmark observation predictions and the action decision are shownin Fig.5.
The robot took different actions even if the starting
position was the same. This is due to the quantization of the observation and variance of the walking.
In this example, the robot started from the center ofthe field as in the first example, but then took otheractions instead ( 1) forward, 2) forward, 3) landmark
observation, 4) forward, 5) landmark observation, 6)
left forward, 7) forward, and 8) forward ). In this experiment, the ball and the target goal were observed
at every moment for decision making. The probability
distributions of landmark observation predictions andthe action decision are shown in Fig.6.
Here is another example starting from the centerright cross mark of the field. In this example, therobot took the actions, 1) left forward, 2) landmark
observation, 3) forward, 4) forward, and 5) left forward. The ball and the target goal were observed atevery moment for decision making. The probability
distributions of landmark observation prediction andthe action decision are shown in Fig.7.

Figure 5: Probability distribution in Experiment 1-1(The gray scale of each box indicates the probability.
Darkest 1 and lightest 0.).
Figure 6: Probability distribution in Experiment 1-2.
We show the number of re-observations in Table
3.2. Each number indicates the number of trials, total
steps, re-observations, and the rate of re-observations.
We see that the number of re-observation is reduced
to about half of the total steps.
Table 4: The number of needed observation (Experiment 1).
begin
from
center
left
right

3.3

# of
trials121216# of total
steps
35
31
64

# of
re-ovserv.
18
15
38

rate ofre-observ.
.51
.48
.59

Experiment 2

In the same field we trained the robot with regard to
the games of the RoboCup 99. In this experiment, weplaced the robot and the ball at many more locations
than in experiment 1. To reduce the load of teaching,
we prepared six actions, forward, left forward, rightforward, left rotation, right rotation, and track theball. Each action is performed for 4.8 seconds.

By this training, we obtained 1364 data points.
Deleting inappropriate data, we used 856 data points
for the action decision tree and 1364 data points forthe ball and landmarks predictions. We show the sizes
and the order of the trees based on the information
criterion in Tables 5 and 6. We used these data for
the RoboCup 99 and the robot showed the movementthat was expected though the robot did look for thelandmarks more frequently than anticipated.

4

Discussions and conclusions

From Experiment 1, we see that the action probability distributions have either a sharp peak (nearly
equal to 1.0) or a very flat profile. When the action probability profile is flat, the landmark probability profile, which is important for decision making,is also flat due to poor training data for making prediction trees. Then, the robot looked all around to
search the landmarks and the ball.
Comparing the order of action and landmarks inprediction trees between Experiment 1 and Experi-Table 6: The order of information of trees (Experiment 2).
1
2
3
4
5
6
7
8
9
action: ball TG OG SW SE NW NE CE CW
ball: ball act
OG: OG SE SW TG NW CW NE CE act
TG: TG OG SE SW NW NE CW CE act
SE: SE OG TG SW CE NE NW CW act
SW: SW OG CW SE TG NW NE CE act
CE: CE SE OG TG NE SW NW act CW
CW: CW SW OG TG NW SE NE CE act
NE: TG NE OG SE CE NW SW CW act
NW: NW TG OG SW CW SE NE CE act

this method for memory consumption and simplicity,
might be changed as ID3 or C4.5 for further abstraction and observation efficiency.
Figure 7: Probability distribution in Experiment 1-3.

Table 5: Depth and size of the trees (Experiment 2).
# of leaves min dep. mean dep. max dep.
action: 586
2
5.89
9
ball: 403
2
2
2
OG: 958
2
7.58
9
TG: 1050
2
7.67
9
SE: 8452
7.35
9
SW: 901
2
7.41
9
CE: 9012
7.13
9
CW: 8732
7.37
9
NE: 103127.60
9
NW: 9802
7.55
9ment 2, we notice that the action is higher priority inExperiment 1 than in Experiment 2. It seems that inExperiment 1 the training data was too few to extract
the fact that prediction of landmarks highly depends
on its location, which indicates prediction can be done
mostly by landmark observation. Note that although
the order is different in both cases, they are extracted
from the training data by information criterion andare therefore optimal in that sense. Although the proposed method does not depend on it, the training data
should be sufficient to accomplish the task.
In this paper, we quantized the appearance spaceby hand. But, by using a method like C4.5 [5] formaking action decision trees, quantization may be selforganized. The order in the tree, which is fixed in

Acknowledgments
We thank SONY Digital Creatures Laboratory forproviding us the opportunity to use the legged robots.

References[1] W. Burgard, D. Fox, and S. Thrun. Active mobile
robot localization. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence(IJCAI). Morgan Kaufmann, San Mateo, CA, 1997.
[2] I. Moon, J. Miura, and Y. Shirai. Dynamic motion
planning for efficient visual navigation under uncertainty. In Y. Kakazu, M. Wada, and T. Sato, editors, In
Proc. of the Intelligent Autonomous Systems 5, pages
172–179, 1998.
[3] I. H. Moon, J. Miura, Y. Yanagi, and Y. Shirai. Planning of vision-based navigation for mobile robot under
uncertainty. In Proceedings of the 1997 IEEE/RSJ International Conference on Intelligent Robots and Systems, volume 1, pages 1202–1207, 1997.
[4] J. R. Quinlan. Discovering rules from large collectionsof examples: a case study. In D. Michie, editor, Expert
Systems in the Microelectronic Age. University Press,
Edinburgh, Scotland, 1979.
[5] J. R. Quinlan. C4.5: PROGRAMS FOR MACHINELEARNING. Morgan Kaufmann Publishers, 1993.
[6] J. Tani, J. Yamamoto, and H. Nishi. Dynamical interactions between learning, visual attention, and behavior: An experiment with a vision-based mobile robot.
In P. Husbands and I. Harvey, editors, Fourth European Conference on Artificial Life, pages 309–317. The
MIT Press, 1997.