Acquiring a Global Lexicon
for Identifying Landmarks
in a Heterogeneous Multi-Robot System
Seiji Yamada and Daisuke Katou
CISS, IGSSE
Tokyo Institute of Technology
4259 Nagatsuta, Midori, Yokohama 226-8502, JAPAN
yamada@ymd.dis.titech.ac.jp
Abstract. This paper describes a multi-robot system in which mobile robots try to name landmarks distinctively using a discrimination
game framework. Landmark-based navigation eﬀectively reduces cumulative errors by identifying landmarks and adjusting robot’s localization.
Also it can be applied to a multi-robot system straightforward. However there is a signiﬁcant problem on ﬁnding common names of landmarks among robots. In multi-robot planning, all the landmarks needto have unique names shared by all the robots. Since robots actually
recognize only physical features of a landmark, each robot needs to obtain mappings between the names and the distinctive features of otherlandmarks. We call the search such mappings a landmark naming problem. In this paper, we propose the application of a discrimination game
to solve the landmark naming problem in a heterogeneous multi-robot
system in recognition. Robots autonomously name landmarks throughlocal communications on the landmarks. First we deﬁne a landmark
naming problem and explain a framework to which our approach is applicable. Then we describe a procedure of discrimination game applied
to a multi-robot system. Using the procedure, multiple robots moves,
communicates each other on landmarks, and gradually acquire lexicons
as the mappings. They eventually obtain lexicons with names identifying unique landmark for every robot. Finally we made preliminary
experiments and discuss the results.

1

Introduction

In robotics, a lot of studies on navigation for a mobile robot have been done thus far.
One of the major navigation methods is landmark-based approach [5] [4][9] which copeswith the cumulative errors due to dead-reckoning. The landmark-based navigation eliminates such errors by identifying the landmarks and adjusting robot’s localization using
the information on them. Though the landmark-based navigation can be also applied
to a multi-robot system straightforward, there is a signiﬁcant problem on landmark
naming among robots with diﬀerent recognition. In multi-robot path planning under
the landmark-based navigation, all the landmarks need to have unique names and all
the robots need to recognize the same landmark by the name. Since all that a robot
actually recognizes on a landmark are its physical features, not names, each robot needs
to have mappings between the names and the features. Furthermore the features must
be distinctive of other neighbor landmarks for unique naming. However designing suchmappings is diﬃcult, and we call it a landmark naming problem.

The multiple mobile robots easily becomes heterogeneous in their recognition because of the diﬀerence in their sensors. Some robots may sense the color feature of alandmark using a vision system, others may sense its shape using a range ﬁnder. In
such a heterogeneous multi-robot system, the features mapped from the same name may
be diﬀerent depending on robots and no common feature of the same landmark may
be recognized by robots. In this case, a landmark naming problem may become morediﬃcult. Though a landmark naming problem is a important issue in a multi-robot
system, it hardly has been dealt with thus far.
In this paper, we propose the application of a discrimination game[6][7] to solve thelandmark naming problem in a heterogeneous multi-robot system in recognition. In
our approach, robots autonomously names landmarks through local communications
on the landmarks. First we deﬁne a landmark naming problem in more detail andexplain a framework to which our approach is applicable. Next we describe a procedureof discrimination game applied to a multi-robot system. Using the procedure, multiple
robots moves, communicates each other on landmarks, and gradually acquire lexicons:
mappings from a name of a landmark to physical features. They eventually obtain
global lexicons with names identifying unique landmark for every robot. Finally wemade experiments and discuss the results.
Komoriya proposed a method to select useful landmarks from a set of various
landmarks[3]. Unfortunately the landmark selection is used for a single robot navigation and did not deal with a landmark naming problem. Hager et al. proposed theimage-based extraction method of landmarks[2][1]. However they did not propose themethod for naming in a heterogeneous multi-robot system in recognition. Steels formalized discrimination game and made various experiments for investigating language
development in A-Life fashion[6][7]. As results, interesting phenomena like the occurrence of dialect were observed. We extend the framework to deal with a multi-robot
system.
2

A landmark naming problem

2.1 Framework
We deﬁne a framework to which our approach is applied. The framework is a system
consisting of multiple mobile robots in which the following assumptions hold. We
consider the assumptions are practical and satisﬁed in the most of real environments.
– Local communication : A robot is able to communicate with other robots withina certain distance from it. Most communication systems like wireless communication satisfy this assumption. Strings are available for communication.
– Direct landmark recognition : Even when robots can not identify the same landmark using lexicon, they recognize the landmark directly using a pointer like arobot arm or a laser pointer. Thus, when two robots communicate on a landmark
which is recognized by them, the landmark is identiﬁed for them. However weneed useful lexicon for identifying all the landmark even when two robots can notdirectly point them in path planning.
– Heterogeneous recognition : The features of a landmark which robots can recognize
are diﬀerent depending on the robots’ sensors. No common feature of the same
landmark may be recognized by robots.

2.2 A landmark naming problem
We formalize the landmark naming problem. In such a multi-robot system satisfying
the above assumptions, let r ∈ R be a robot, l ∈ L be a segmented landmark, q ∈ Q bea name and a physical feature f ∈ F which a landmark have and a robot recognizes.
Feature f is not q named by a robot and robots try to assign q to f . Thus the samefeature f may be assigned by diﬀerent names depending robots.
A landmark l has physical features Fl , which is a subset of F , and a robot incompletely recognizes them. Thus a robot recognizes some features and not other ones.
Also a robot r has features F r : a subset of F which it can recognize. Hence the features of a landmark l which a robot r can recognize is described Flr = F r ∩ Fl . Since
all that a robot r actually recognizes on a landmark l are a physical features Flr , notname. Since robots identify a landmark by communication using its name, they tries
to construct a lexicon: a mapping from a name q of a landmark l to recognized features
Flr .
The lexicon of a robot r is deﬁned as Xr : a set of ql ⇒ Elr : a mapping from a nameql to Elr ⊆ Flr for a landmark l. Several robots are able to identify the same landmark
by the same name corresponding to diﬀerent features in each robot’s lexicon.
For implementing a multi-robot system in which robots does planning with interaction each other and have only local information, the lexicon needs to satisfy thefollowing preconditions.
– Globally common names: The name of the same landmark needs to be common in
all the robots’ lexicons. This enables all the robots to identify the same landmark
with the same name for multi-agent planning. This condition is necessary for
multi-agent planning because all robots need to identify landmarks with the names
for planning.
– Locally distinctive features: If several landmarks exist in the area in which a robot
r can recognize, r needs to distinguish a target landmark t (called a topic) fromothers. Thus the Etr needs to be locally distinctive of other landmarks’ Elr s, andsuch Etr is called a distinctive feature set. The recognized landmarks except t
are called background B. Hence the distinctive feature set of r, t, B, is a setrr
Dt,B⊆ Ftr so that ∀b ∈ B, Dt,B⊆ Fbr .
We deﬁne a landmark naming problem as searching the lexicon satisfying the above
two conditions in an environment mentioned earlier. Though this problem has hardly
been dealt with thus far in a multi-robot system, we consider it an essential issue for apractical multi-robot system.
Fig.1 shows an example for a heterogeneous multi-robot system ﬁnding distinctive
feature set. In this case, two robots r1 and r2 observe and point the topic t. Thus othertwo landmarks l1 and l2 construct the background B = {l1 , l2 } to t. For each robot,
Flr s are computed like in Fig.1. Since F r1 is diﬀerent from F r2 , Flr1 may be diﬀerentr1∈ {{f5 }, {f1 , f5 }, {f4 , f5 },from Flr2 . Using Ftr1 , Flr11 , Flr21 , the r1 determines Dt,B
r2
r2
r2
r1
{f1 , f4 , f5 }}. Then by Ft , Fl1 , Fl2 , the r2 computes Dt,B ∈ {{f3 }, {f2 , f3 }, {f3 , f4 }},{f2 , f4 }, {f2 , f3 , f4 }}. After generating the distinctive feature sets, all the robot needto construct a lexicon with globally common names.

l2
l1

F l 2 = { f1 , f4 }F l 1 = { f1 , f2 , f9 }t
F t = { f1 , f2 , f3 , f4 , f 5 }r2

r1

F r1 = { f1 , f4 , f5 , f 6 , f 7}
F tr1 = { f1 , f4 , f 5 }rr

Ft 2 = { f2 , f3 , f 4 }r

F l11 = { f1 }F l 2 = { f2 }r
Fl 1 = { f1 , f4 }2

r
Fl 2 = { f4 }2

Figure 13r

F 2 = { f2 , f3 , f4 }1

A heterogeneous multi-robot system in recognition.

Discrimination game for a multi-robot system

To solve the landmark naming problem, we utilize the discrimination game[6][7]. Unfortunately the general discrimination game was not constructed for a multi-robot system,
thus we need to extend it. The followings show a procedure of discrimination game fora single mobile robot in a multi-robot system. Brieﬂy a speaker robot sends a namecorresponding to a distinctive feature set and the other hearer robot receives it. If thehearer can identify the landmark using features mapped from the sent name in its own
lexicon, the communication is successful and the name is evaluated positively. Communications like this occur suﬃciently between robots and the lexicons satisfying above
two condition will be obtained gradually. Also the cumulative success frequency S is
assigned to all the mappings in a lexicon.
1. A robot moves constantly with a movement strategy. A robot becomes a speaker
robot rs when landmarks and a hearer robot rh are recognized within its communication area.
2. The rs select one of recognized landmarks as a topic t and points it. Then the rh
identiﬁes it directly, and the two robots identify the same landmark.
3. A speaker procedure and a hearer procedure are executed and the communication
is processed.
• Speaker procedurerss and selects one of them for communication.
(s1) The rs computes Dt,Brsrs(s2) For the selected Dt,B
, the rs extracts qt from qt ⇒ Dt,Bin Xrs .
rs
rs
If no mapping for the Dt,B in Xrs , qt ⇒ Dt,B is added into Xrs . The qt isselected from Q. This communication ﬁnishes in failure.
If several mappings exist, rs uses the mapping with maximum S.

(s3) The rs sends the qt to rh . If the success acknowledgement is returned fromrh , this communication ﬁnishes successfully, and otherwise in failure. Thenrs
is updated.
S of qt ⇒ Dt,B
• Hearer procedure(h1) The rh receives the qt from rs , and extracts corresponding features Et in Xrh .
rhFurthermore it extracts all the own distinctive feature sets Dt,Bs.
(h2) If the Et is Drht,B , the rh can identify t by a name and this communicationﬁnishes successfully. Then rh sends the success acknowledgement to rs , andS of the mapping is increased.
If the Et is not distinctive, this communication ﬁnishes in failure and rh add
all the qt ⇒ Drh t,B into Xrh .
We explain an example for Fig.1. Let r1 and r2 have Xr1 = {au ⇒ {f5 }, ba ⇒{f4 , f5 }} and Xr2 = {au ⇒ {f3 }, ba ⇒ {f2 }, nu ⇒ {f3 , f4 }} respectively. At step1, let
r1 and r2 be a speaker robot and a hearer robot. Then r1 selects t as a topic, and l1 ,l2 become background B. Also r1 points t, and r2 recognizes it directly at step2. Next
r1=
r1 starts a speaker procedure. At step(s1), r1 computes distinctive feature sets Dt,B
{f5 }, {f1 , f5 }, {f4 , f5 }, {f1 , f4 , f5 } as mentioned in §2.2, and selects {f5 }. The r1 ﬁnds
a mapping au ⇒ {f5 } for {f5 } in its Xr1 , and extracts the name au at step(s2). As aresult, r1 sends au to r2 and S is increased at step(s3). This speaker procedure ﬁnishes.
On the other hand, the hearer robot r2 receives au and obtains the corresponding
feature {f3 } from au ⇒ {f3 } in Xr2 at step(h1). Since the {f3 } is a distinctive feature set
r2
Dt,B, r2 can identify the topic and this communication ﬁnishes successfully at step(h2).
Then S of au ⇒ {f3 } is increased.
If the speaker robot r1 selects {f4 , f5 } and its name ba is sent to r2 , this communication ﬁnishes in failure. Because the corresponding feature set {f2 } to ba in Xr2 is notr2∈ {{f3 }, {f2 , f3 }, {f3 , f4 }, {f2 , f4 },
distinctive. As a result, r2 adds all the ba ⇒ Dt,B
{f2 , f3 , f4 }} into Xr2 at step(h2).
4Experiments

4.1 Experimental Settings
For investigating the utility of our approach, we made preliminary experiments in a
simple multi-robot system. The following experimental settings were used. The Fr and
Fl are shown in Table.1. Using these settings, we investigated the acquisition of a global
common lexicon.
– Movement strategy : random walk.
– Robots : R = {r1 , r2 , r3 }– Landmarks : L = {l1 , l2 , l3 }. Landmarks are positioned randomly.
– Names : Q = {ci, du, ba}

– Feature set : F = {f1 , · · · , f9 }– Environment size : 10×10 cells.
– Communication area size : a circle with radius 4.
– The terminal number of communications : 1,000 times.

4.2 Experimental results
cumulative number of success communications. forFig.2 shows the average success rates = the thecumulative number of communications.
landmarks. Seeing from this graph, the communications gradually became better. Also
we observed the communications got almost successful eventually.
The lexicons obtained ﬁnally are shown in Table.2, where only the mappings withthe highest S are indicated. In the lexicons, the same landmark is assigned with thesame name and all the feature sets mapped from the names are distinctive. This meansthat the lexicons satisfying the two conditions: Globally common names and Locallydistinctive features, have been obtained by robots. Note that through the acquiring
the lexicons, no centralized mechanism is necessary and all the robots autonomously
behave. Though the experimental results were obtained under a single initial condition,
we veriﬁed the feasibility of our approach to the landmark naming problem.
In landmark-based navigation, such a common naming system is quite necessary tomulti-robot planning because robots need to identify landmarks using common names
for planning and recognize the landmarks using physical features as executing a plan.

5

Conclusion

We deﬁned the landmark naming problem in a heterogeneous multi-robot system inrecognition and proposed a method to solve it using a discrimination game framework.
In our system, robots autonomously name landmarks through local communications
on the landmarks. We explained the background causing a landmark naming problem
and described a framework to which our approach is applicable. Then we extended
the procedures of a discrimination game for applying to a multi-robot system in which
agents may move and sense locally. Using the procedure, multiple robots moves, communicates each other on landmarks, and gradually acquire lexicons as the mappings.
Finally we made preliminary experiments in a simple multi-robot system and found out
our approach is promising to solve the landmark naming problem.
Unfortunately there are open problems as the followings.
– Strategy for eﬃciency: Since the random walk is not eﬃcient movement strategy for our framework, we are currently developing more eﬃcient and eﬀective
movement strategy. We also consider selective communication strategy in which

Fr1
Fr2
Fr3

{f4 , f7 , f5 , f8 , f6 , f9 }
{f1 , f7 , f2 , f8 , f3 , f9 }
{f1 , f4 , f2 , f5 , f3 , f6 }Table 1

Fl1
Fl2
Fl3

Fr and Fl .

{f1 , f4 , f7 }
{f2 , f5 , f8 }
{f3 , f6 , f9 }The average success rate.

0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0

0

100

200

300

400

500

600

700

800

900

1000

Communication times.

Figure 2 The average success rate through communications.

l1
l2
l3

Xr1
ci ⇒ {f4 }du ⇒ {f8 }ba ⇒ {f9 }Xr2ci ⇒ {f1 }du ⇒ {f8 }ba ⇒ {f3 }Xr3ci ⇒ {f1 }du ⇒ {f5 }ba ⇒ {f6 }Table 2 The obtained global lexicon.

a robot communicates with the other robot depending on its success rate, lexicon
and so on. Furthermore we may be able to apply evolutionary robotics approach
like [8] to automatically acquire suitable behavior rules for eﬃcient solution of
the landmark naming problem. By coding behavior rule validly and designing aﬁtness function, genetic algorithm/programming searches eﬃcient strategy.
– Systematic experiments: The experiments are preliminary because they are restricted in a simple environment with a small number of robot, landmarks andfeatures. Thus we need to systematically make large experiments using simulation. By the experiments, we investigate the coverage, the limitation of ourapproach and the robustness against initial positions of robots, landmarks.
– Implementation on real mobile robots: Our ﬁnal target is to implementation of
our system into a real multi-robot system. For achieving this purpose, we need toreﬁne the formalization of our framework and the assumption on the environment.
By experiments with real mobile robots, we can ﬁnd out the gap between simulation and a real environment and the eﬃciency of acquiring the global lexicons
becomes still more signiﬁcant.

References[1] Z. Dodds and G. Hager. A color interest operator for landmark-based navigation. In
Proceedings of the Fourteenth National Conference on Artiﬁcial Intelligence, 1997.
[2] G. Hager, D. Kriegman, E. Yeh, and C. Rasmussen. Image-based prediction of landmark features for mobile navigation. In Proceedings of the 1997 IEEE International
Conference on Robotics and Automation, pages 1040–1046, 1997.
[3] K. Komoriya, E. Oyama, and K. Tani. Planning of landmark measurement for thenavigation of a mobile robot. In Proceedings of the 1992 IEEE/RSJ International
Conference on Intelligent Robots and Systems, pages 1476–1481, 1992.
[4] S. Maeyama, A. Ohya, and S. Yuta. Outdoor landmark map generation throughhuman assisted route teaching for mobile robot navigation. In Proceedings of the1996 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages
957–962, 1996.
[5] T. D’ Orazio, M. Ianigro, E. Stella, and A. Dstante. Self-location of a mobile
robot using visual landmarks. In Proceedings of the 1992 IEEE/RSJ International
Conference on Intelligent Robots and Systems, pages 1869–1874, 1992.
[6] L. Steels. Emergent adaptive lexicon. In Proceedings of the Fourth International
Conference on Simulation of Adaptive Behavior, pages 562–567, 1996.
[7] Luc Steels. Perceptually grounded meaning creation. In Proceedings of the Second
International Conference on Multi Agent Systems, pages 338–344, 1996.
[8] S. Yamada. Evolutionary design of behaviors for action-based environment modelingby a mobile robot. In Genetic and Evolutionary Computation Conference, 2000. to
appear.
[9] T. Yamamoto, S. Maeyama, A. Ohya, and S. Yuta. An implementation of landmarkbased position estimation function as an autonomous and distributed system for amobile robot. In Proceedings of the 1999 IEEE/RSJ International Conference onIntelligent Robots and Systems, pages 1141–1148, 1999.