Module 5 - Chapter 3
Module 5 - Chapter 3
Advisory Board:
Luigia Carlucci Aiello Alan Mackworth
Franz Baader Mark Maybury
Wolfgang Bibel Tom Mitchell
Leonard Bolc Johanna D. Moore
Craig Boutilier Stephen H. Muggleton
Ron Brachman Bernhard Nebel
Bruce G. Buchanan Sharon Oviatt
Anthony Cohn Luis Pereira
Artur d’Avila Garcez Lu Ruqian
Luis Fariñas del Cerro Stuart Russell
Koichi Furukawa Erik Sandewall
Georg Gottlob Luc Steels
Patrick J. Hayes Oliviero Stock
James A. Hendler Peter Stone
Anthony Jameson Gerhard Strube
Nick Jennings Katia Sycara
Aravind K. Joshi Milind Tambe
Hans Kamp Hidehiko Tanaka
Martin Kay Sebastian Thrun
Hiroaki Kitano Junichi Tsujii
Robert Kowalski Kurt VanLehn
Sarit Kraus Andrei Voronkov
Maurizio Lenzerini Toby Walsh
Hector Levesque Bonnie Webber
John Lloyd
Srikanta Patnaik
Robot Cognition
and Navigation
An Experiment with Mobile Robots
Managing Editors:
Prof. Dov M. Gabbay
Augustus De Morgan Professor of Logic
Department of Computer Science, King’s College London
Strand, London WC2R 2LS, UK
Prof. Dr. Jörg Siekmann
Forschungsbereich Deduktions- und Multiagentensysteme, DFKI
Stuhlsatzenweg 3, Geb. 43, 66123 Saarbrücken, Germany
ISSN 1611-2482
ISBN 978-3-540-23446-3 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material
is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broad-
casting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of
this publication or parts thereof is permitted only under the provisions of the German Copyright Law
of September 9, 1965, in its current version, and permission for use must always be obtained from
Springer. Violations are liable for prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
[Link]
c Springer-Verlag Berlin Heidelberg 2007
Printed in Germany
The use of general descriptive names, registered names, trademarks, etc. in this publication does not
imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
Typesetting: by the author
Production: Integra Software Services Pvt. Ltd., Puducherry, India
Cover Design: KünkelLopka, Heidelberg
Printed on acid-free paper 45/3180/Integra 5 4 3 2 1 0
To my wife
Priti
and my sons
The author would like to thank Ingeborg Mayer and Ronan Nugent of
Springer for their kind cooperation in connection with writing this book.
The author wishes to express his deep gratitude to his parents, who always
stood by him throughout his life. Last but not least, the author wishes to
thank his wife Priti for her tolerance and forbearance of his indifference to
family life and her assistance in many ways for the successful completion
of the book. He also conveys special thanks to his sons Sritam and Priyam
for their sacrifice and tolerance during the writing of the book.
2 Map Building…………………………………………………... 21
2.1 Introduction............................................................................. 21
2.2 Constructing a 2D World Map................................................ 22
2.2.1 Data Structure for Map Building................................... 22
2.2.2 Explanation of the Algorithm........................................ 26
2.2.3 An Illustration of Procedure Traverse Boundary.. 27
2.2.4 An Illustration of Procedure Map Building ............ 29
2.2.5 Robot Simulation........................................................... 31
2.3 Execution of the Map Building Program ................................ 33
2.4 Summary................................................................................. 38
XII Contents
References............................................................................................... 283
Index........................................................................................................ 289
1 Cybernetic View of Robot Cognition
and Perception
In 1986, Rodney A. Brooks was the first man to use the findings of
ethological research, and to design a mobile robot. He published a seminal
paper on the subsumption architecture, which was fundamentally a differ-
ent approach in the development of mobile robots [Arbib, 1981]. He de-
veloped the subsumption language that would allow him to model some-
thing analogous to animal behaviors in tight sense-act loops using
asynchronous finite-state machines. The first type of behavior for a robot
was used to avoid obstacles that are too close and moving a little away or
else standing still. Secondly, higher level behavior might be to move the
robot in a given direction. This behavior would dominate the obstacle-
avoidance behavior by suppressing its output to the actuators unless an ob-
ject comes too close. The higher levels subsumed the lower levels, and
therefore the name of the architecture was subsumption architecture. They
were able to develop a robot, using simple sonar or infrared sensors that
could wander around a laboratory for hours without colliding into objects
or moving people. After this development, Brooks and his colleagues de-
veloped highly mobile robots, i.e. mobots, both wheeled and legged, which
could chase moving objects or people and run or hide from light. Further,
they can negotiate a cluttered landscape which might be found in a rugged
outdoor environment.
During the 1990s, there were many developments such as HERBERT: a
soda-can-collecting robot [Connell, 1990]; GENGHIS: a robot that learned
to walk [Maes & Brooks, 1990; Brooks, 1989]; TOTO: a hallway-
navigating robot [Matric, 1992]; and POLLY: a tour-guide robot
[Horswill, 1993]. The idea was to build up capability in the robot through
behaviors that run in parallel to achieving possible alternative goals. The be-
havior in these robots was able to execute various actions on a priority
basis or to achieve various goals within the cycle time. After this develop-
ment, the world model was distributed among the types of behaviors with
only relevant parts of the model being processed for each behavior. The
generation of simple plans for path planning and the compilation of the
result of actions could be done before run time by using these types of
behaviors.
Today, researchers are trying to develop intelligent machines after a
careful and meticulous review of human cognition, soft computing tools
and techniques. But there are still open problems in these areas of machine
learning and perception, which are being investigated using many alterna-
tive approaches. This research work mainly aims at studying various tech-
niques of perception and learning, using the cognitive model, and their ap-
plications in mobile robots. Detailed programs have been provided in the
respective chapters.
1.1 Introduction to the Model of Cognition 3
Fig. 1.1. Three cycles namely acquisition, perception and learning and coordina-
tion, with their states in the model of cognition. LTM = Long Term Memory;
STM = Short Term Memory
4 1 Cybernetic View of Robot Cognition and Perception
extraction of features from the sensed data, along with stored knowledge in
LTM. For example, visual information on reception is filtered from unde-
sirable noise, and the elementary features like size, shape, color are ex-
tracted and stored in STM [Borenstain, 1996].
Reasoning: Generally this state constructs high level knowledge from ac-
quired information of relatively lower level and organizes it in structural
form for efficient access [Bharick, 1984]. The process of reasoning analy-
ses the semantic or meaningful behavior of the low level knowledge and
their association [Chang, 1986]. It can be modeled by a number of tech-
niques such as commonsense reasoning, causal reasoning, non-monotonic
reasoning, default reasoning, fuzzy reasoning, spatial and temporal reason-
ing, and meta-level reasoning [Popovic et al., 1994].
Attention: This is responsible for the processing of a certain part of the in-
formation more extensively, while the remaining part is neglected or sup-
pressed. Generally, it is task-specific visual processing which is adopted
by animal visual systems [Matlin, 1984]. For instance, finding out the area
of interest in a scene autonomously is an act of attention.
Action and coordination: This state determines the control commands for
various actuators to execute the schedule of the action plan of a given
problem, which is carried out through a process of supervised learning
[Maes & Brooks, 1990]. The state also coordinates between various de-
sired actions and the input stimuli.
Acquisition cycle: The task of the acquisition cycle is to store the infor-
mation temporarily in STM after sensing the information through various
sensory organs. Then it compares the response of the STM with already
acquired and permanently stored information in LTM. The process of rep-
resentation of the information for storage and retrieval from LTM is a
critical job, which is known as knowledge representation. It is not yet
known how human beings store, retrieve and use the information from
LTM.
Vision is the most powerful sense organ of human beings and it is also the
key sensory device for a mobile robot. So far, not much progress has yet
been achieved in visual perception of a mobile robot due to limitations in
hardware and software. Visual processing requires specialized hardware and
cameras, which are quite large to fit into the mobile robot. Secondly, tradi-
tional software for vision processing is very poor in quality, because it re-
quires complete analysis of the entire scene even to recognize a minute ob-
ject. Further, detection of an obstacle in front of the robot using stereovision
takes a longer time, which is not at all permissible for online navigation.
As there is a shift in paradigm towards the behavioral model, research-
ers have started examining animal models for both motor control and per-
ception. The research findings reveal that the frog uses simple visual mo-
tion detection to catch flying prey and bees depend on specific aspects of
the color spectrum for their search. Psychological study indicates that the
human visual system supports very simple behavior. Low resolution pe-
ripheral vision is used to watch for indications of motion, for instance col-
lision with looming objects, whereas the high resolution fovea is used to
gather information for reasoning about an object. Human vision does not
perceive everything in all its color, motion and temporal dimensions at one
time but direct attention is given to a very narrow portion of the visual
field based on the task they are performing. As a result of this study, the
paradigm in vision is shifted to a philosophy where perception exists to
support the behavior of robots [Murphy et al., 1998].
Dickmann studied two major principles of perception during the 1980s.
The first one was about the evolving process and internal representation of
the world, which is known as Schopenhauer’s idea of perception, and the
second one was Kant’s theory of the true reality of perception. With these
two principles, Dickmann could represent various systems, including real
time constraint using the notion of space and time [Zavidovique, 2002].
Human beings acquire knowledge of their surroundings unconsciously
during their first years of crawling, then walking and reacting. Let us dis-
cuss a little more, the physiology and anatomy of the human visual system,
which may help in understanding robot vision.
The human visual system converts energy in the visible spectrum into ac-
tion potentials in the optic nerves. The wavelength of visible light ranges
8 1 Cybernetic View of Robot Cognition and Perception
Fig. 1.2. A schematic diagram of human vision. n = nodal point, AnB and anb are
similar triangles. In this diagram, the nodal point is 15 mm from the retina. All re-
fraction is assumed to take place at the surface of the cornea, 5 mm from the nodal
point. The dotted lines represent rays of light diverging from A and refracted at the
cornea so that they are focused on the retina at ‘a’
from approximately 390 nm to 720 nm. In the human eye, light is actually
refracted at the anterior surface of the cornea and at the anterior and poste-
rior surface of the lens. The process of refraction is shown schematically
in Fig. 1.2.
The images of objects in the environment are focused on the retina. The
light rays striking the retina generate potential changes that initiate action
potentials on photosensitive compounds such as rods and cones. When the
compound absorbs light, the structure changes and triggers a sequence of
events that initiate neural activity. The human eye contains about 130 mil-
lion rods and approximately 8 million cones. Rods are monochrome re-
ceptors of light, and cones are sensitive to color, which are different parts
of the spectrum [Seculer et al., 1990]. The distribution of rods and cones in
the retina is very irregular. The detailed spatial representation of the retina
is in the form of electrical responses transmitted to the lateral geniculate
nucleus (LGN) via retinal ganglion cells (RGC). Subsequently, LGN pro-
jects a similar point-to-point representation on the visual cortex, where
these electrical responses produce the sensation of vision.
Initially, the aim of the robot vision designer was to build the simplest
possible system that was necessary to solve a given task and use its per-
formance to improve its architecture. Horswill has developed a low cost
vision system for navigation called the POLLY System, where the devel-
opment team has used active, purposeful and task-based vision [Horswill,
1993], which computes the specific information needed to solve specific
tasks. Murphy has introduced another model of sensing organization called
action-oriented perception for a mobile robot, with multiple sensors per-
forming locomotive tasks [Murphy, 1998], and work on robot vision and
perception is still continuing as a major research topic.
Instead of storing templates for entire shapes, the feature-based model util-
izes a series of feature detectors. Generally the features included are of a
geometric type such as vertical and horizontal lines, curves and angles.
Feature detectors may be used either at every position in the input array, or
may be used for the global image. In case of multiple feature detectors, the
degree of matching is estimated for the target feature with respect to each
section of the input array. The levels of activation for each feature may be
summed up across the input array by providing a set of numbers for each
feature. This list of numbers in the form of a vector of weights for different
features is used as the stored representation of the object. The objective is
12 1 Cybernetic View of Robot Cognition and Perception
to define the shape of the object with invariant features, which are inde-
pendent of locations. The process of recognition consists of finding the
best match between the stored representations and the levels of activation
of the feature detectors in the input image.
The structural model contains information about the relative positions and
relationships between parts of an object. This structural description is
stored in memory in the form of a data structure such as a list or tree or
graph of predicates. The representation is often depicted as a graph, where
nodes correspond to the parts or the properties, and the edges correspond
to the spatial relations [Minsky, 1975]. The advantage of structural repre-
sentation is that it factors apart the information in a scene without losing
any part of it. This model enables us to represent the object with the help
of a list of labels and also their relative position and orientation with
respect to the human observer. Various spatial reasoning operations may
be performed by specifying the shape, location, orientation and spatial
1.4 Machine Learning 13
relationship of one set of objects with other objects in another set. The rec-
ognition process can be improved by including statistical and logical
operations. The use of structural descriptions appears to be preferred
because of computational convenience.
The work of David Marr [Marr, 1982] is one of the best examples of the
computational approach to the recognition problem, which is the most in-
fluential contemporary model of 3D shape recognition. Marr introduced
the need to determine edges of an object and constructed a 2½ D model,
which carries more information than 2D but less than a 3D image. Thus
an approximate guess about the 3D object can be framed from its 2½ D
images.
Since the invention of the computer there was always the question of how
to make them learn. If we could understand how to program them to learn,
i.e. to improve automatically with experience, it would have been a great
achievement. A successful understanding of how to make them learn
would open up many new uses of computers and new levels of competence
and customization. Further, a detailed understanding of machine learning
might lead to further investigation of human learning ability and disabili-
ties. Machine learning algorithms have been investigated by a number of
researchers. These are effective for certain types of learning tasks and as a
result a theoretical understanding of learning started to emerge. Broadly
speaking learning means any computer program that improves its perform-
ance for some tasks through experience.
ALVINN system [Pomerleau et al., 1989] has used its learned strategies to
drive unassisted at 70 miles/hour for 90 minutes on public highways
among other cars. Similar techniques have possible applications in many
sensor-based control systems. This learning problem of autonomous driven
systems can be formally defined as
Machine learning can be broadly classified into three categories: (i) su-
pervised learning, (ii) unsupervised learning and (iii) reinforcement
learning. Supervised learning requires a trainer, who supplies the input–
output training instances. The learning system adapts its parameters using
some algorithms to generate the desired output patterns from a given input
pattern. But, in the absence of trainers, the desired output for a given input
instance is not known, and consequently the learner has to adapt its pa-
rameters autonomously. This type of learning is termed unsupervised
learning. There is a third type of learning, known as reinforcement learn-
ing, which bridges the gap between supervised and unsupervised catego-
ries. In reinforcement learning, the learner does not explicitly know the
input–output instances, but it receives some form of feedback from its en-
vironment. The feedback signals help the learner to decide whether its ac-
tion on the environment is rewarding or punishable. The learner thus
16 1 Cybernetic View of Robot Cognition and Perception
adapts its parameters based on the states of its actions, i.e. rewarding or
punishable. Recently, a fourth category of learning has emerged from the
disciplines of knowledge engineering, which is known as inductive logic
programming [Konar, 2000].
Fuzzy logic deals with fuzzy sets and logical connectives for modeling
the human-like reasoning problems of the real world. A fuzzy set, unlike
conventional sets, includes all elements of the universal set of the domain
with varying membership values in the interval [0,1]. It may be noted
that a conventional set contains its members with a membership value
equal to one and disregards other elements of the universal set with a
zero membership value. The most common operators applied to fuzzy
sets are AND (minimum), OR (maximum) and negation (complementa-
tion), where AND and OR have binary arguments, while negation has a
unary argument. The logic of Fuzzy Set Theory was proposed by Zadeh
[Zadeh, 1983], who introduced the concept of system theory, and later
extended it for approximate reasoning in expert systems. Other pioneer-
ing research contributions on Fuzzy Logic include the work of Tanaka in
stability analysis of control systems [Tanaka, 1995], Mamdani in cement
kiln control [Mamdani, 1977], Kosko [Kosko, 1994] and Pedrycz
[Pedrycz, 1995] in Fuzzy Neural Nets, Bezdek in Pattern Classification
[Bezdek, 1991], and Zimmerman [Zimmerman, 1991] and Yager [Yager,
1983] in Fuzzy Tools and Techniques.
Fuzzy logic has become a popular tool for robot cognition in recent
years [Saffioti, 1997]. Given the uncertain and incomplete information
about the environment available to the autonomous robot, fuzzy rules pro-
vide an attractive means for mapping ambiguous sensor data to appropriate
information in real time. The methodology of fuzzy logic appears very
useful when the processes are too complex for analysis by conventional
quantitative techniques or when the available sources of information are
interpreted qualitatively, inexactly, or uncertainly, which is the case with
mobile robots. However, fuzzy logic parameters are usually determined by
domain experts using a trial and error method. Also, as the number of input
variables increases, in the case of mobile robots, the number of rules in-
creases exponentially, and this creates much difficulty in determining a
large number of rules.
Genetic algorithms (GAs) are stochastic in nature, and mimic the natural
process of biological evolution [Rich et al., 1996]. This algorithm borrows
the principle of Darwinism, which rests on the fundamental belief of the
survival of the fittest in the process of natural selection of species. GAs find
extensive applications in intelligent search, machine learning and optimization
20 1 Cybernetic View of Robot Cognition and Perception
In step (i) a few initial problem states are first identified and in step (ii) a
fixed number of better candidate states are selected from the generated
population. Step (iii) evolves a new generation through the process of
crossover and mutation. These steps are repeated a finite number of times
to obtain the solution for the given problem.
GAs have been successfully applied to solve a variety of theoretical and
practical problems by imitating the underlying processes of evolution, such
as selection, recombination, and mutation. The GA-based approach is a
well-accepted technique for enabling systems to adapt to different control
tasks [Filho, 1994]. But, it is not feasible for a simple GA to learn online and
adapt in real time. The situation is worsened by the fact that most GA meth-
ods developed so far assume that the solution space is fixed, thus preventing
them from being used in real-time applications [Michalewicz, 1986].
1.6 Summary
2.1 Introduction
The phrase map building [Patnaik et al., 1998] refers to the construction
of a map of the work space autonomously by the robot, which enables the
robot to plan the optimal path to the goal. Map building helps the mobile
robot to become conversant with the world around it. The information
about the neighborhood world of the robot is thus required to be encoded
in the form of a knowledge base. For the purpose of navigational plan-
ning, a mobile robot must acquire knowledge about its environment. This
chapter demonstrates the scope of map building of a mobile robot of its
workspace.
It is evident from the discussion in the last chapter that the acquisition of
knowledge is a pertinent factor in the process of building perception. Hu-
man beings can acquire knowledge from their environment through a
process of automated learning. Machines too can acquire knowledge by
sensing and integrating consistent sensory information. A number of tech-
niques are prevalent for automated acquisition of knowledge. The most
common among them are unsupervised and reinforcement learning tech-
niques. In an unsupervised learning scheme, the system updates its pa-
rameter by the analyzing consistency of the incoming sensory information.
Reinforcement learning, on the other hand, employs a recursive learning
rule that adopts the parameters of the systems, until convergence occurs,
following which the parameters become time invariant. The chapter in-
cludes a technique for constructing a 2D world map by a point mass robot
with its program written in C++.
22 2 Map Building
It is assumed that the height of the robot is less than that of the obstacles
within the workspace. In fact, most of the navigational problems for robots
are confined to two-dimensional environments. The algorithm for map
building in a 2D environment is given below.
There exist two different types of algorithms for automated map build-
ing. The first one refers to landmark-based map building [Taylor et al.,
1998]and the second one is metric-based map building [Asada, 1990;
Elfes, 1987; Pagac et al., 1998]. Offline map building is discussed here
utilizing a metric-based approach [Patnaik et al., 1998]. Further, to main-
tain the order in the traversal of the robot around the obstacles, a directed
search is preferred here. The depth-first search, which is a directed search
technique, is being utilized here.
Let us consider a circular mobile robot (shown in Fig. 2.1) that can orient
itself in any of the following eight directions: north (N), north-east (NE),
east (E), south-east (SE), south (S), south-west (SW), west (W) and north-
west (NW).
NW NE
W Robot E
SW SE
Fig. 2.1. The representation of a circular robot with eight ultrasonic sensors
around it in eight geographical directions
2.2 Constructing a 2D World Map 23
If there is an obstacle in N
Then move to the nearest obstacle in N
If there is an obstacle in NE
Then move to the nearest obstacle in NE
If there is an obstacle in E
Then move to the nearest obstacle in E
………………………………………………
………………………………………………
If there is an obstacle in NW
Then move to the nearest obstacle in NW
If the above steps are executed recursively, then the robot would have a
tendency to move to the north so long as there is an obstacle in the north,
else it moves north-east. The process is thus continued until all the obsta-
cles are visited. Another point needs to be noted here, that after moving to
an obstacle, the robot should move around it to identify the boundary of
the obstacles. Thus when all the obstacles are visited a map representing
the boundary of all obstacles will be created. This map is hereafter referred
to as the 2D world map of the robot. Two procedures are given below, i.e.
Map Building and Traverse Boundary. In the procedure Map
Building a linked list structure is used with four fields. The first two
fields, xi, yi denote the coordinate of the point visited by the robot. The
third field points to the structures containing the obstacle to be visited next,
and the fourth field denotes the pointer to the next point to be visited on
the same obstacle. A schematic diagram depicting the data structure is pre-
sented in Fig. 2.2. Another data structure is used in procedure Map
Building for acquiring the boundary points visited around an obstacle.
This structure has three fields, the first two correspond to the xi, yi coordi-
nate of one visited point on the obstacle i, while the third field is a pointer
which corresponds to the next point on obstacle i. A schematic diagram for
this pointer definition is presented in Fig. 2.3.
24 2 Map Building
xi yi
Fig. 2.2. Definition of one structure with two pointers, used for acquiring the list
of visited obstacles
xi yi
Fig. 2.3. Definition of another structure with one pointer for acquiring the bound-
ary points visited around an obstacle
Proof: By completeness of the algorithm, we mean that it will visit all ob-
stacles and the floor boundary before termination.
N NE E SE S SW W NW
The shaded portions are obstacle regions. So we choose the location (70,
48) (in the west direction) as the next location to move, since it is an ob-
stacle-free point and it is next to an obstacle region. So the robot will move
to a step ahead in the west direction.
28 2 Map Building
(75,43) NORTH
(70,43)
(80,43)
(70,48) (80,48)
R
(50,50)
(100,50)
(70,50) (80,50)
W
E
E (75,50)
A
S
S
T
T
(50,100) (100,100)
SOUTH
Fig. 2.4. The robot near a rectangular obstacle showing the sensory information in
the eight specified directions
Let us consider the robot at another position (48, 48) shown in Fig. 2.5.
The sensory information of the robot at this new location is given as fol-
lows.
N NE E SE S SW W NW
From the above table, it is clear that the location (48, 53) is in the south di-
rection, which is obstacle-free and it is next to the obstacle location (53,
53). So the next point to move is (48, 53) in the south direction. Likewise
we repeat this process until we reach the initial coordinates (75, 48). The
coordinates of the boundary of the obstacle are stored in a linked list,
which is maintained in a general structure. Now the next task is to build
the total map with the help of this boundary traversing algorithm, which is
illustrated below.
2.2 Constructing a 2D World Map 29
(48,43)
(43,43) (53,43)
NORTH
(43,48) R (53,48)
(100,50)
(43,53) (50,50)
(48,53)
W E
E A
S S
T T
Fig. 2.5. The robot near a square-type obstacle at another location and the sensor
information in the simulation
An example is given here for creation of a linked list to record the visited
obstacles and their boundaries of an environment shown in Fig. 2.6.
The searching process is started from the north direction of robot. If
any obstacle is found, the robot will move to that obstacle and record
the boundary coordinate information of that obstacle. Again it will start
searching in the north direction from the recently visited obstacle. In
this way it will go as deep as possible in the north direction only. If no
new obstacle is available in the north direction, the robot will look for
other directions, in order, for new obstacles. If any new one is found,
the robot will visit it and move as deep as possible in the newly found
direction. If in any case it cannot find any new obstacle, it will back-
track to its parent obstacle and start looking in other directions, as
shown in Fig. 2.7.
30 2 Map Building
NORTH
(0,100) (100,100)
(70,70) (90,70)
(25,70) (40,70)
A
C
W (25,60)
E
(75,65) (85,65) A
E (40,60)
S S
T T
START (35,55)
(25,40)
(35,40)
D
(90,20)
(70,20)
(20,30) (35,30)
B
(90,10)
(70,10)
Fig. 2.6. The path traveled by the robot while building the 2D world map using
depth-first traversal. The obstacles are represented with literals and the coordi-
nates of the obstacles and the workspace is shown inside the braces
2.2 Constructing a 2D World Map 31
Coordinates of
starting point
35 55
3 6 40 60 40 70 25 70 25 60
90 10 90 20 70 20 70 10
85 65 90 70 70 70 75 65
35 40 25 40 20 30 35 30
Fig. 2.7. The linked list created to record the visited obstacles and their boundary.
Here all the points on the boundary visited by the robot have not been shown in
the linked list in order to maintain clarity
The algorithm for map building has been simulated and tested by a C++
program. An artificial workspace has been created with nine obstacles along
with a closed room, which is shown in Fig. 2.8. The workspace dimension is
fixed by four corner points having coordinates (80, 80), (400, 80), (400, 400)
and (80, 400) in a (640, 480) resolution screen. The dimensions of the obsta-
cles, described by their peripheral vertices, are as follows:
Obstacle 1: (140,120), (170,100), (185,120), (175,140)
Obstacle 2: (240,120), (270,140), (225,164), (210, 135)
32 2 Map Building
The source code is available in Listing 2.1 at the website of the book. The
dimension of the soft mobile object is 10 pixels in diameter. The soft ob-
ject starts at position (100, 380), and moves as per the map building algo-
rithm, which is displayed in Fig. 2.9 and the simulation results are shown
in Fig. 2.10.
80
120
160 S
200
240
280
N
320
360
400
The simulation results given in Fig. 2.10 and the coordinates of the
boundaries visited by the robot are given subsequently.
34 2 Map Building
(i): Showing starting position of Robot (ii): After visiting First Obstacle.
(iii): After visiting 2nd Obstacle (iv): After visiting 3rd Obstacle
(v): After visiting 4th Obstacle (vi): After visiting 5th Obstacle
2.3 Execution of the Map Building Program 35
(100,398)(104,398)(108,398)(112,398)(116,398)(120,398)(
124,398)(128,398)(132,398)(136,398)(140,398)(144,398)(1
48,398)(152,398)(156,398)(160,398)(164,398)(168,398)(17
2,398)(176,398)(180,398)(184,398)(188,398)(192,398)(196
,398)(200,398)(204,398)(208,398)(212,398)(216,398)(220,
398)(224,398)(228,398)(232,398)(236,398)(240,398)(244,3
98)(248,398)(252,398)(256,398)(260,398)(264,398)(268,39
8)(272,398)(276,398)(280,398)(284,398)(288,398)(292,398
)(296,398)(300,398)(304,398)(308,398)(312,398)(316,398)
(320,398)(324,398)(328,398)(332,398)(336,398)(340,398)(
344,398)(348,398)(352,398)(356,398)(360,398)(364,398)(3
68,398)(372,398)(376,398)(380,398)(384,398)(388,398)(39
2,398)(396,398)(400,398)(400,394)(400,390)(400,386)(400
,382)(400,378)(400,374)(400,370)(400,366)(400,362)(400,
358)(400,354)(400,350)(400,346)(400,342)(400,338)(400,3
34)(400,330)(400,326)(400,322)(400,318)(400,314)(400,31
0)(400,306)(400,302)(400,298)(400,294)(400,290)(400,286
)(400,282)(400,278)(400,274)(400,270)(400,266)(400,262)
(400,258)(400,254)(400,250)(400,246)(400,242)(400,238)(
400,234)(400,230)(400,226)(400,222)(400,218)(400,214)(4
00,210)(400,206)(400,202)(400,198)(400,194)(400,190)(40
0,186)(400,182)(400,178)(400,174)(400,170)(400,166)(400
,162)(400,158)(400,154)(400,150)(400,146)(400,142)(400,
138)(400,134)(400,130)(400,126)(400,122)(400,118)(400,1
14)(400,110)(400,106)(400,102)(400,98)(400,94)(400,90)(
400,86)(400,82)(396,82)(392,82)(388,82)(384,82)(380,82)
(376,82)(372,82)(368,82)(364,82)(360,82)(356,82)(352,82
)(348,82)(344,82)(340,82)(336,82)(332,82)(328,82)(324,8
2)(320,82)(316,82)(312,82)(308,82)(304,82)(300,82)(296,
82)(292,82)(288,82)(284,82)(280,82)(276,82)(272,82)(268
,82)(264,82)(260,82)(256,82)(252,82)(248,82)(244,82)(24
0,82)(236,82)(232,82)(228,82)(224,82)(220,82)(216,82)(2
12,82)(208,82)(204,82)(200,82)(196,82)(192,82)(188,82)(
184,82)(180,82)(176,82)(172,82)(168,82)(164,82)(160,82)
(156,82)(152,82)(148,82)(144,82)(140,82)(136,82)(132,82
)(128,82)(124,82)(120,82)(116,82)(112,82)(108,82)(104,8
2)(100,82)(96,82)(92,82)(88,82)(84,82)(80,82)(80,86)(80
,90)(80,94)(80,98)(80,102)(80,106)(80,110)(80,114)(80,1
18)(80,122)(80,126)(80,130)(80,134)(80,138)(80,142)(80,
146)(80,150)(80,154)(80,158)(80,162)(80,166)(80,170)(80
2.3 Execution of the Map Building Program 37
,174)(80,178)(80,182)(80,186)(80,190)(80,194)(80,198)(8
0,202)(80,206)(80,210)(80,214)(80,218)(80,222)(80,226)(
80,230)(80,234)(80,238)(80,242)(80,246)(80,250)(80,254)
(80,258)(80,262)(80,266)(80,270)(80,274)(80,278)(80,282
)(80,286)(80,290)(80,294)(80,298)(80,302)(80,306)(80,31
0)(80,314)(80,318)(80,322)(80,326)(80,330)(80,334)(80,3
38)(80,342)(80,346)(80,350)(80,354)(80,358)(80,362)(80,
366)(80,370)(80,374)(80,378)(80,382)(80,386)(80,390)(80
,394)(80,398)(84,398)(88,398)(92,398)(96,398)(100,398)
Obstacle Boundary
(168,99)(172,99)(176,103)(180,107)(180,111)(184,115)(18
8,119)(188,123)(184,127)(184,131)(180,135)(180,139)(176
,143)(172,143)(168,139)(164,139)(160,135)(156,131)(152,
131)(148,127)(144,127)(140,123)(136,119)(140,115)(144,1
15)(148,111)(152,107)(156,107)(160,103)(164,99)(168,99)
Obstacle Boundary
(176,161)(180,157)(184,161)(188,165)(192,169)(196,173)(
200,177)(204,181)(200,185)(196,189)(192,193)(192,197)(1
88,201)(184,201)(180,197)(176,193)(172,189)(172,185)(16
8,181)(168,177)(168,173)(172,169)(172,165)(176,161)
Obstacle Boundary
(180,238)(180,242)(176,246)(172,250)(168,254)(164,258)(
160,258)(156,262)(152,266)(148,270)(144,274)(140,274)(1
36,278)(132,282)(128,282)(124,278)(124,274)(120,270)(12
0,266)(116,262)(112,258)(112,254)(108,250)(108,246)(108
,242)(112,238)(116,234)(120,230)(124,226)(128,222)(132,
222)(136,222)(140,226)(144,226)(148,226)(152,230)(156,2
30)(160,230)(164,230)(168,234)(172,234)(176,234)(180,23
8)
Obstacle Boundary
(180,338)(184,334)(188,330)(192,330)(196,334)(200,338)(
204,342)(208,346)(212,350)(208,354)(204,358)(200,362)(1
96,362)(192,366)(188,370)(184,370)(180,374)(176,370)(17
6,366)(172,362)(172,358)(168,354)(168,350)(172,346)(176
,342)(180,338)
Obstacle Boundary
(212,142)(208,138)(208,134)(212,130)(216,130)(220,126)(
224,126)(228,122)(232,122)(236,118)(240,118)(244,118)(2
48,122)(252,126)(256,126)(260,130)(264,134)(268,134)(27
2,138)(272,142)(268,146)(264,146)(260,150)(256,150)(252
,154)(248,154)(244,158)(240,158)(236,162)(232,162)(228,
166)(224,166)(220,162)(220,158)(216,154)(216,150)(212,1
46)(212,142)
Obstacle Boundary
(244,174)(248,174)(252,174)(256,178)(260,182)(264,182)(
268,186)(272,190)(276,190)(280,194)(284,194)(288,198)(2
84,202)(280,206)(276,206)(272,206)(268,206)(264,206)(26
38 2 Map Building
0,206)(256,206)(252,206)(248,202)(244,202)(240,198)(236
,198)(232,194)(228,190)(232,186)(236,182)(240,178)(244,
174)
Obstacle Boundary
(268,248)(272,252)(268,256)(268,260)(264,264)(260,268)(
260,272)(256,276)(252,280)(248,284)(244,284)(240,284)(2
36,284)(232,284)(228,284)(224,284)(220,284)(216,280)(22
0,276)(220,272)(220,268)(224,264)(224,260)(228,256)(232
,256)(236,252)(240,252)(244,252)(248,252)(252,252)(256,
248)(260,248)(264,248)(268,248)
Obstacle Boundary
(232,300)(236,304)(240,308)(240,312)(244,316)(248,320)(
248,324)(252,328)(252,332)(248,336)(244,336)(240,340)(2
36,340)(232,344)(228,340)(224,336)(224,332)(220,328)(22
0,324)(216,320)(220,316)(220,312)(224,308)(224,304)(228
,300)(232,300)
Obstacle Boundary
(297,251)(297,247)(297,243)(297,239)(301,235)(301,231)(
301,227)(305,223)(305,219)(305,215)(309,211)(313,215)(3
17,215)(321,219)(325,219)(329,223)(333,223)(337,227)(34
1,227)(345,231)(349,231)(353,235)(357,235)(361,239)(361
,243)(357,247)(353,251)(349,255)(345,259)(341,263)(337,
267)(333,271)(329,271)(325,271)(321,267)(317,267)(313,2
63)(309,259)(305,259)(301,255)(297,251)
2.4 Summary
3.1 Introduction
(a) (b)
Fig. 3.1 (a) Cell distance calculation by cellular automata; (b) Collision free path
3.3 Path Optimization by the Quadtree Approach 41
search technique. If it fails, it will reject that path and start navigating in
the next shortest path, and so on.
• A Mobile robot ordinarily negotiates any given path only once, which
implies that it is more important to develop a negotiable path quickly
than to develop an “optimal” path, which is usually an expensive affair.
• The Mobile robot should keep a safe distance from obstacles in the en-
vironment.
3.3.2 Definition
The quadtree is a tree, where each node has four child nodes. Any two-
dimensional map can be represented in the form of quadtree by recursive
decomposition [Davis, 1986]. Each node in the tree represents a square
block of the given map. The size of the square block may be different from
node to node. The nodes in the quadtree can be classified into three groups
i.e. free nodes, obstacle nodes and mixed nodes.
• A free node is a node where no obstacles are present in the square re-
gion.
• An obstacle node is a node whose square region is totally filled with
obstacles.
• A mixed node’s square region is partially filled with obstacles.
The generation process of the 2D map shown in Fig. 3.2(a) is first divided
into four subsquare regions (four child nodes), namely NW, NE, SW, SE
according to the directions. Here square regions NW, SW are fully occu-
pied with obstacles (gray regions) and are called the “obstacle node”, node
NE does not have any obstacle in it and is called a “free node”. The node
SE is partially filled with the obstacle and is called “mixed node”. The de-
composition is shown in Fig. 3.2(b). Free nodes and obstacle nodes are not
decomposed further and remain as leaf nodes. But the mixed node is sub-
divided into four subquadrants, which form children of that node. The de-
composition procedure is repeated until either of the conditions mentioned
below is satisfied.
Let us consider the map shown in Fig. 3.3, for the generation of the quad-
tree. The data structure needed for a node is represented as given below in
programming language C syntax.
Struct node
{ node* pointer_to_child1;
node* pointer_to_child2;
node* pointer_to_child3;
node* pointer_to_child4;
node* pointer_to_parent_node;
int node_status;
};
NORTH
WEST EAST
NW NE SE SW
SOUTH
(a) (b)
Fig. 3.2 (a) Representation of a simple 2D world map, in which the gray region
represents obstacles; (b) Decomposition of the 2D world map into quadtree nodes.
The type of each node is represented by the small box, with different fill patterns:
gray color for obstacle nodes, white color for free nodes, and hatched boxes for
mixed nodes
44 3 Path Planning
NW child B NE child C
SW child D SE child E
The gray square areas in Fig. 3.3 are regions occupied by obstacles. In
the first stage of decomposition, the map is divided into four square re-
gions of equal size as shown in Fig. 3.4. The root of the quadtree is the
map itself and is denoted by A.
In the above decomposition the child E contains no obstacle and re-
mains as a leaf node. The remaining nodes B, C, and D contain obstacles
and are treated as mixed nodes. The quadtree after first decomposition is
represented as in Fig. 3.5. The small square box under each node repre-
sents the status of the node, where the white box, gray box and the hashed
line box represents a free node, obstacle node and a mixed node, respec-
tively. The obstacle nodes are decomposed further, as shown in Fig. 3.6.
3.3 Path Optimization by the Quadtree Approach 45
NW
SW
NE
SE
B C D
E
NW NE NW NE NW NE
SW SE SW SE SW SE
B C D
F G H I J K L M N O P Q
NW NE SE SW NW NE SE SW NW NE SE SW
NW NE NW NE
SW SE SW SE
F G
R S T U V W X Y
NW NE SE SW NW NE SE SW
E
D
C
J K L M N O P Q
F G H I
R S T U V W X Y
Fig. 3.8. The Qaudtree representation of the world map given in Fig. 3.3
3.4 Neighbor-Finding Algorithms for the Quadtree 47
North
A B
West
East
D E
C
F G
South
Fig. 3.9. A simple 2D world map
48 3 Path Planning
A B
C D
In Fig. 3.10, let us assume the robot is in the square region A, and the
goal is to reach the square region D. If we take the corner neighborhood
into account, the regions A and D will become neighbors. But there is no
path to move into the region D from region A, since regions B and C are
occupied with obstacles. This is the reason why the corner neighbors are
neglected. As mentioned earlier, for a mixed node, one can get four imme-
diate children in four directions. These are called NW, NE, SE, and SW,
which are below in Fig. 3.11.
If P is a node, and I is a quadrant, then these fields are referenced as
FATHER (P) and SON (P, I), respectively. One can determine the specific
quadrant in which a node P lies relative to its father by the use of the func-
tion SONTYPE (P), which has the value of I, if
SON (FATHER(P),I) = P.
For instance assume Fig. 3.11 is a node named P, and the child node in the
NW direction is named as Q. Then
FATHER ( Q ) = P.
SON( P,NW ) =Q.
SONTYPE (P) = NW.
North
NW NE
West SW SE East
South
Fig. 3.11. Representation of children used in the algorithm
3.4 Neighbor-Finding Algorithms for the Quadtree 49
While generating the quadtree the “node status” is stored in every node.
The integer values stored for the node status are
(ii) REFLECT ( B,I ) yields the SONTYPE value of the block of equal size
that is adjacent to the side B of a block having SONTYPE value I. For in-
stance,
REFLECT(E,NW) = NE and REFLECT( N,SW ) = NW.
REFLECT gives the mirror image of the node I in the direction B. For Fig.
3.9, the mirror image of child SW in the N (north) direction is NW and the
mirror image of child SW in the E (east) direction is SE. These relations
are represented in the tables shown in Fig. 3.12.
For the quadtree corresponding to a 2n × 2n array, the root is at level n,
and the node at level i, is at a distance n−i from the root of the tree. In
other words, for a node at level i, we must ascend n−i FATHER links to
reach the root of the tree. The following algorithm explains how to reach
the neighboring node.
50 3 Path Planning
ADJ (S,Q)
Quadrant ‘Q’
NW NE SW SE
N T T F F
Side ‘S’ E F T F T
S F F T T
W T F T F
REFLECT (S,Q)
Quadrant ‘Q’
NW NE SW SE
N SW SE NW NE
Side ‘S’ E NE NW SE SW
S SW SE NW NE
W NE NW SE SW
Begin
Value node P;
Value direction D;
Node Q;
If ( not NULL(FATHER(P)) and ADJ(D,SONTYPE(P))
Then
/* find common ancestor */
Q← GTEQUAL_ADJ_NEIGHBOR(FATHER(P),D)
Else
Q← FATHER(P);
3.4 Neighbor-Finding Algorithms for the Quadtree 51
This algorithm will return a neighbor of greater or equal size. This is done
by finding the common ancestor first. Next the path is retraced while mak-
ing the mirror image move about an axis formed by the common boundary
between the blocks associated with the nodes. The common ancestor is
simple to determine. For instance, to find an eastern neighbor, the common
ancestor is the first ancestor node which is reached via its NW or SW son.
The procedure is shown in Fig. 3.13.
In Fig. 3.13, the eastern neighbor of the node A is G. It is located by
ascending the tree until the common ancestor D, is found, from Fig. 3.14.
This requires going through a NE link to B, a NE link to C, and a NW link
to reach D. The node G is now reached by backtracking along the previous
path with appropriate mirror image moves. This requires descending a NE
link to reach E (since NW and NE are horizontal mirror images), a NW
link to reach F and a NW link to reach G.
Fig. 3.13. Finding the neighbor of node A using a mirror image path from a com-
mon ancestor
52 3 Path Planning
NW NE
C E SW SE
NE NW
B F
NE NW
A G
Fig. 3.14. Finding the neighbor of node A using a mirror image path from a com-
mon ancestor
After finding the equal-size neighbor, if it has any children, the smaller
neighbors in it can be found by reaching every leaf node of it and, with the
coordinate information available at that leaf node, checking the adjacency.
The greater sized neighbor can be easily found from the given algorithm. It
is the node which has no children, in the backtracking path, even though
backtracking is not complete. After getting all neighbor nodes, the best
neighbor node is selected among them, using an A* algorithm, which is
explained in the next section.
From the knowledge of the starting and goal points, with a single traversal
of the quadtree the stating node (S) and goal node (G) can be identified.
Here the task is to find the minimum cost path between the starting node
and goal node. For this purpose the A* algorithm is employed with the
evaluation function f, of a node C which is defined as
the generated cost of a path should depend on both the actual distance trav-
eled and the clearance of the path from the obstacles, g(c) is defined as
g( c ) = g( p ) + g'( p,c )
where g (p) is the cost of the path from S to C’s predecessor P on the path
and g' (p, c) is the cost of the path segment between P and C.
The latter function, g'(p, c), in turn is defined as
g'(p, c)= D(p, c) + α . d(c )
with D(c) representing the actual distance between nodes P and C, given
as half the sum of the node sizes, and d(c) representing the cost incurred by
including node C on the path. d(c) depends upon the clearance of the node
C from the nearby obstacles. A linear shape for the cost function d can be
chosen defining d(c) as
d (c) = Omax − O(c)
where O(c) is the distance of the node C from the nearest obstacle given by
the quadtree distance transform and Omax is the maximum such distance for
any node in the quadtree, so that d(c) is always positive. α in the equation
for g'(p, c) is a positive constant which determines how far the resultant
path will avoid obstacles.
The function h(c) is calculated as the Euclidean distance between mid-
points of the regions represented by C and G. Along with this single crite-
rion, two more criteria can be included. They are the number of obstacles
intersecting the straight line path between C and G, and the second is the
total area of the obstacles intersecting the straight line path between C and
G. After calculating the evaluation function for all the neighbors of the
starting node, the lowest cost function is chosen among them and the node
(say X) corresponding to it is selected as the best node to move. The proc-
ess of finding all neighbors and finding the best of them and then moving
to it, is repeated for the node X. This process is repeated until the goal
node is reached. The source code of the program Path Planning using
the quadtree method is available in Listing 3.1 at the website of the book
and the execution has been given in the next section.
54 3 Path Planning
3.7 Summary
4.1 Introduction
When the map of the robot’s environment is known, it can plan its trajec-
tory before navigation to a predefined goal point from the starting point.
But, many times the robot cannot decide about the entire trajectory before
navigation, because the obstacles change their positions over time. Further,
in a dynamic environment, which includes one or more mobile objects, it
is useless to plan a path before navigation. In this situation, a robot plans a
subpath and thus navigates to that point and the process continues until the
robot reaches the destination. While moving towards the subgoal, if it dis-
covers an obstacle, then it retraces back to the previous point and then re-
plans for an alternative subpath. The process of replanning and navigation
may continue until the robot reaches a given goal point [Patnaik et al.,
1999c]. In this chapter navigational planning will be discussed using evo-
lutionary algorithms [Patnaik et al., 1998].
The evolution program is a probabilistic algorithm, which maintains a
population of individuals, P(i)= { xii , …, xni } at iteration i. Each individ-
ual represents a potential solution to the problem at hand, and each solu-
tion xit is evaluated to give some measure of its “fitness”. Then, a new
population at iteration (i + 1) is formed by selecting the better suited indi-
viduals. Some members of this population undergo transformations by
means of unary transformations mi (mutation), which create new individu-
als by a small change in a single individual (mi: SÆS), and higher order
transformations like cj (crossover), which create new individuals by com-
bining parts from several (two or more) individuals (cj: S×SÆ S). After
several generations, the program converges to a near optimum solution,
hopefully representing the best individual. The structure of an evolution
program is shown below.
60 4 Navigation Using a Genetic Algorithm
(a) Select two parent chromosomes from a population according to their fitness.
The better the fitness, the bigger the chance to be selected. This step is called
Selection.
(b) Crossover the parents to form a new offspring or children, with a crossover
probability. If no crossover was performed, the offspring are an exact copy of
the parents.
(c) Mutate new offspring at each locus or position in the chromosome, with a mu-
tation probability (this step is called mutation) and place these new offspring
in the population.
(d) Use the newly generated population for a further run of the algorithm. This
process is called replacement.
Step 4: If the predefined condition is satisfied then stop and return the best solu-
tion in current population or else Goto Step 2.
This is a generalized algorithm, but there are many variations, which can
be implemented differently for different problems. Next the question is to
create chromosomes, and what kind of encoding one should follow to se-
lect parents for crossover. This can be achieved in many ways, but the al-
gorithm should select the better parents. While selecting the new popula-
tion from the generated offspring, it may sometimes loose the best
chromosome. In order to overcome this at least one best solution must be
copied without changes to a new population, so that the best solution found
at any iteration can survive to the end of the run.
The chromosome should in some way contain information about the solu-
tion which it represents. The most common way of encoding is a binary
string, which can be represented as shown in Table 4.1.
Each chromosome has one binary string. Each bit in this string can
represent some characteristic of the solution or the whole string can repre-
sent a number. Of course, there are many other schemes of encoding,
which depend mainly on the problems to be solved. For instance, one can
encode integer or real numbers directly, which is sometimes useful for
some specific problems.
62 4 Navigation Using a Genetic Algorithm
4.2.2 Crossover
Crossover selects genes from parent chromosomes and creates a new off-
spring. The simplest way to do this is to choose randomly some crossover
point and copy everything before this point from first parent and then copy
everything after the crossover point from the second parent. There exist
also many complicated crossover like, multipoint and ring crossover,
which depends on the encoding scheme of the chromosome. The specific
crossover designed for a specific problem may not be suitable for other
problems. A sample cross over operation is shown in Table 4.2.
4.2.3 Mutation
4.2.4 Parameters of a GA
There are two basic parameters of a GA, i.e. the crossover probability and
the mutation probability. The crossover probability says how often cross-
over will be performed. If there is no crossover, i.e. 0% probability, the
offspring is an exact copy of the parents. If there is full crossover, or 100%
probability, then all offspring are made by crossover. The objective of the
crossover is that new chromosomes will have good parts of old chromo-
somes and some of the new chromosomes which are better will be
evolved. However, it is good to let some parts of the population survive to
the next generation, which are really better chromosomes. The mutation
probability says how often parts of the chromosome will be mutated. If
there is no mutation, or 0% probability, offspring are taken after crossover
or copied without any change. If the mutation probability is 100%, the
whole chromosome is changed. Mutation is made to prevent the GA fal-
ling into local extremum, but it should not occur very often, otherwise the
GA will behave as random search.
There are also some other parameters of a GA, one of which is popula-
tion size, which specifies how many chromosomes should be in the popu-
lation in one generation. If there are too few chromosomes, the GA have
few possibilities to perform a crossover and only a small part of the search
space is explored. On the other hand, if there are too many chromosomes,
the evolution process slows down.
4.2.5 Selection
Xi Yi Xj Yj
Fig. 4.1. Representation of the chromosome of a single path segment from the sen-
sory readings
4.3 Navigation by a Genetic Algorithm 65
Crossover
Offspring generated
may either encounter obstacles or fall outside the workspace. Hence inte-
ger crossover is chosen instead of binary crossover. In Fig. 4.2 the cross-
over point is set between the third and the fourth field for each pair of
chromosomes and the new population is generated. For the newly gener-
ated populations the feasibility is estimated, i.e. whether these paths are
obstacle free or not. The next, mutation is performed for fine-tuning the
path to avoid the sharp turns.
The estimation of fitness of each and every chromosome is done subse-
quently, out of the total population (both for the initial and new popula-
tions), which invloves finding the sum of the Euclidean distance from the
starting point to the coordinate obtained from the sensor information and
the distance from that point to the goal point.
found after each generation. The third and fourth fields of the best-fit
chromosome become the next intermediate point to move and the starting
point is updated with the best-fit point. The whole process of the GA, from
setting up the initial population, is repeated until the best-fit chromosome
has its third and fourth field equal to the x- and y-coordinates of the goal
location. The algorithm is formally presented below and the detailed code
is given in the next section.
Repeat
i) Initialization:
Get sensor information in all possible directions
(xj1, yj1), (xj2,yj2),….(xjn,yjn).
Form chromosomes like (xi,yi,xj,yj);
ii) Crossover:
Select crossover point randomly on the third and
the fourth fields of the chromosome.
Allow crossover between all chromosomes and get
new population. (xi,yi,xj1,yj1),(xi,yi,xj2,yj2),
(xi,yi,xj1i,yj1i),(xi,yi,xj2ii,yj2ii);
iii) Mutation:
Select a mutation point in bitstream randomly and
complement that bit position for every chromosome.
iv) Selection:
Discard all chromosomes (xi,yi,xj,yj) from
population whose line segment is on obstacle
region
For all chromosomes in population find fittness
using Fittness(xi,yi,xj,yj) = 1/ ((xj-xi)2+(yj-yi)2
+(xg-xj)2+(yg-yj)2 );
Identify the best fit chromosome (xi,yi,xbf,ybf);
Add to path-list(xbf,ybf);
xi=xbf; yi=ybf;
End for,
Until ( xi=xg)&&(yi=yg);
End.
4.4 Execution of the GA-Based Navigation Program 67
120
160
200
240
280
320
360
400
Fig. 4.3. Workspace with nine obstacles. The point-mass robot navigates from the
starting point to the goal position smoothly
68 4 Navigation Using a Genetic Algorithm
120
160
200
240
280
320
360
400
Fig. 4.4. Obstacle F has moved to a new location blocking the free path to the
goal. The robot navigates in an alternative path using EA
In the situation shown in Fig. 4.4, the robot has to replan the path with the
new situation, which can be achieved by memorizing the path by temporal
associative memory which is described here.
considered a two-layered neural net, where neurons in each layer are con-
nected to the neurons in the other layer through bi-directional links. The
signal associated with the neurons can assume {−1, +1} values and the
weights, describing the connectivity between the neurons possess signed
integer values. The basic problem in BAM was to design a single set of
weight matrix W, such that the difference between the transformed vector
and the output vector is a minimum.
∑ (A W − B ) + ∑ (B W
∀i
i i
∀i
i
T
− Ai ) (4.1)
A1→ A2
A2→ A3
…………
…………
An-1→ An
Let us assume that the whole sequence from Ai through An and from Aj
through Bn is stored. Now it has been detected that the sequence Aj+1 to An
is invalid. The system under this configuration will backtrack from Aj+1 to
Aj by the operation Aj = Aj+1 .WT and then proceed through an alternative
sequence through Bi by the transformation Bi = Aj.W′. This property of
TAM encourages employing it in replanning of the navigation of the
mobile robot. Thus, it may be inferred that TAM may be useful for
70 4 Navigation Using a Genetic Algorithm
Once the possible path segments are generated by the EA navigator, the
robot replanning can be encoded by using TAM. The encoding scheme in
the present context is to evaluate the weight matrix W that satisfies the cri-
terion of minimality of the function.
∑ (A W − A
∀i
i i +1 ) + ∑ (A
∀i
i +1 W
T
− Ai ) (4.2)
⎧
k ⎪ 1, if A W ≥ 0
A i+1 = ⎨ i i
⎪0, if A W < 0
⎩ i i
⎧
k ⎪ 1, if A i+1 W T
> 0
A 1 = ⎨ i
⎪ T
⎩0, if A i+1 W i ≤ 0
The trajectories traversed by the soft mobile object along two alternative
paths, shown in Fig. 4.5 are represented by the following set of sequences
in decimal numbers and later converted to binary values, where the num-
ber of bits depends on the length and resolution.
(a)
(b)
Fig. 4.5 (a) Sample path between starting position (S) and goal position (G)
though a charted path A1, A2, ……A10; (b) mobile object traverses in an alternate
path after backtracking from node A7 to A4, as the semi-dynamic obstacle F has
shifted its position and then navigates through the charted path from B1 to B4 and
then takes the normal path to reach the goal within the workspace
4.5 Replanning by Temporal Associative Memory 73
⎡1 1 −1 1 −1 1 ⎤
⎢1 1 −1 1 −1 1 ⎥
⎢ ⎥
⎢− 1 − 1 1 −1 1 − 1⎥
=⎢ ⎥
⎢1 1 −1 1 −1 1 ⎥
⎢1 1 −1 1 −1 1 ⎥
⎢ ⎥
⎣− 1 − 1 1 −1 1 − 1⎦
⎡ 7 1 1 3 3 5 ⎤
⎢ 1 3 -1 1 -3 -1 ⎥
⎢ ⎥
⎢ -1 -3 - 3 -1 3 - 3⎥
= ⎢ ⎥
⎢ 7 1 1 7 -1 1 ⎥
⎢ 1 5 -3 -1 3 5 ⎥
⎢ ⎥
⎣⎢ -1 1 1 -1 3 -3 ⎦⎥
Encoding the above sequences into bipolar values gives the following:
⎡ 4 0 2 0 2 2 ⎤
⎢- 2 2 0 2 0 0 ⎥⎥
⎢
⎢0 0 -6 0 -2 2⎥
= ⎢ ⎥
⎢ 2 2 0 6 4 4 ⎥
⎢6 -2 0 2 4 4 ⎥
⎢ ⎥
⎣⎢ 2 2 4 2 4 0 ⎦⎥
Fig. 4.7. Robot finds an alternate path by the TAM matrix to reach the goal
4.6 Summary
5.1 Introduction
SVS classes have been used to interface the camera, and the BotSpeak li-
brary functions have been used to synthesize voice feedback from the ro-
bot. This chapter discusses the tools required for robot programming. This
should facilitate better understanding of the codes that are presented in the
subsequent chapters.
The Pioneer 2-DX ActivMedia mobile robot shown in Fig. 5.1, contains
basic components for sensing and navigation in a real-world environ-
ment. It also includes battery power, drive motors and wheels, position–
speed encoders, integrated sensors and accessories like a gripper and ste-
reo camera. The robot is controlled by an onboard microcontroller and
robot server software [Saphira, 1999]. Pioneer 2-DX also contains an ad-
dressable I/O bus for 16 devices, two RS-232 serial ports, eight digital
I/O ports, and five A/D ports, which are accessible through a common
application interface to the robot server software, Pioneer 2 Operating
System (P2OS). The weight of Pioneer 2-DX is 9 kg and it can carry ex-
tra payload of up to 23 kg.
5.2.1 Components
The main components of Pioneer 2-DX include deck(s) and console, body,
nose, and accessory panels and an array of eight sonar sensors in the front
and eight in the rear that provide object detection and navigation. The ro-
bot has reversible-DC motors equipped with a high-resolution optical
quadrature shaft encoder for position and speed sensing and dead reckon-
ing. The major component of the Pioneer 2-DX microcontroller is a 20
MHz Siemens 88C166 microprocessor with integrated 32K Flash-ROM
and dynamic RAM of 32K. Information about the robot’s state and con-
nections appears on a 32-character (two lines) liquid-crystal display (LCD)
on the console. The display shows the state of communication with the cli-
ent computer along with the battery voltage. The RESET and MOTORS
push-button switches on the console affect the microcontroller’s logic and
motor-driver systems. The serial communication between microcontroller
and client can be established through the RS-232 port.
The Pioneer 2-DX is mounted with an onboard PC, hard-disk drive, on-
board 10/100 Base-T Ethernet for network access along with 10-BaseT
Ethernet cable to a 10/100 Mbps hub for network access. The operating
system of Pioneer’s onboard PC is LINUX 7.1, which includes networking
features that support remote monitoring and control of the robot’s onboard
systems. Ethernet access is done by the Carrier Sense Multiple Access/
Collision Detection (CSMA/CD) technique and is established using
BreezeNET PRO.11 Series.
The Small Vision System (SVS) is a built-in package for vision process-
ing, which consists of several library functions for image capture and ste-
reo correlation. A video-capture board or boards in the PC digitizes the
video streams into main memory. The SVS library package computes the
disparity image, which can be displayed or processed further. It also in-
cludes a program namely smallv, which is used for standalone vision
processing applications.
5.3 ARIA
ARIA stands for ActivMedia Robotics Interface for Application, and was
designed for use with ActivMedia Robotics mobile robots. The ARIA pro-
gramming library is for C++ object-oriented programmers who want to
have close control of the robot. ARIA is also useful for preparing robot-
control software and deploying it on ActivMedia Robotics mobile robot
platforms.
80 5 Robot Programming Packages
SRI International’s Saphira [Konolige, 1995] has been built upon ARIA
and is useful for creating applications with built-in advanced robotics ca-
pabilities, including gradient navigation and localization, as well as GUI
controls with visual display of robot platform states and sensor readings.
ARIA will be discussed in detail as it gives greater control for building
programs to achieve desired results. The following sections cover the fun-
damental usage of ARIA for programming the mobile robot illustrated by a
simple program whenever required. In detail the features of the package
can be obtained from the ARIA product manual.
After associating the device with the robot, it is required to establish the
client–server connection between ARIA’s ArRobot and the Pioneer 2-
DX microcontroller or SRIsim simulator. The blockingConnect()
method doesn’t return from the call, until a connection succeeds or fails.
ArRangeDevice are range device abstractions of the robot, for which
there are relevant readings. ArSonarDevice has been used for han-
dling sonar readings, which collect 2D data periodically at specific global
coordinates. A RangeDevice is attached to the robot with
void ArRobot::addRangeDevice (ArRangeDevice
*device);
Sonar sensors are integrated with the robot controller and their readings
are automatically included with the standard Server Information Packet
(SIP) and are handled by the standard ArRobot packet handler. None-
theless, it must be explicitly added to the sonar RangeDevice with the
robot object to use the sonar readings for control tasks. Each RangeDe-
vice has two sets of buffers (ArRangeBuffer): current and cumula-
tive, and each supports two different reading formats: box and polar. The
current buffer contains the most recent reading and the cumulative buffer
contains several readings over time.
The ARIA client drives the robot and runs its various accessories
through direct and motion commands, as well as through Actions. At the
very lowest level, one may send commands directly to the robot server
through ArRobot. Direct commands consist of a 1-byte command num-
ber followed by none or more arguments as defined by the robot’s operat-
ing system. Motion commands are explicit movement commands and con-
trol the mobility of the robot, either to set an individual wheel or to
coordinate translational and rotational velocities or to change the robot’s
absolute or relative heading or move a prescribed distance or just stop. The
list of command functions of the robot used for motion commands is given
in Table 5.1.
82 5 Robot Programming Packages
including a priority which determines its position in the action list. Custom
actions can be created by deriving from an abstract class namely,
is the only function that needs to be overloaded for an action to work. Ac-
tions are evaluated by the resolving descending order of priority (lowest
priority goes first) in each ArRobot syncTask cycle just prior to State
Reflection. The resolver goes through the actions to find a single end Ac-
tionDesired (ArActionDesired ()), which defines the exact
action to be performed. At the lowest level the robot’s microcontroller
manages the tasks of robot control and operation, which include move-
ment of the mobile actuator and end-effectors such as motors and gripper,
as well as acquiring sensor information such as sonar or IR beams. The
5.3 ARIA 83
The network setting for the client–server architecture of the robot is as fol-
lows, which will be used in the rest of the programs discussed in the sub-
sequent chapters.
Hostname : [Link]
IP : [Link]
Netmask : [Link]
Default Gateway : [Link]
Primary DNS : [Link]
The first task of any robotic application is to establish and manage client–
server communication between the software client developed in ARIA and
the onboard robot servers and devices. ARIA provides inbuilt support for
this connectivity through its class ArDeviceConnection.
The code fragment given below shows how to establish connection to the
simulator and the robot.
physical robot and is the most important instance in any program using
which all robotic tasks shall be carried out. The instances of ArSerial-
Connection and ArTcpConnection (in this case, serConn and
tcpConn, respectively) are used to establish a connection. The above or-
der ensures that the programs first try to connect to the simulator and if the
simulator is unavailable it tries to connect to the robot server. The set-
Port() function sets the port_id through which the communication is
to take place. If such a communication port is successfully opened then a
client–server connection is established between the program (i.e. the in-
stance of ArRobot) and the onboard robot server, using the setDe-
viceConnection() function of the ArRobot class. In order to ensure
that a non-blocking connection has been established the following lines of
code are used.
if (![Link]())
{printf("Could not connect to robot... Exiting.");
Aria::shutdown();
return(1);
}
5.3.4 ArRobot
ArRobot as has been stated earlier, is an abstraction of the real robot, i.e.
it is the program version of the physical robot. Any function called on the
instance of the ArRobot class applies to the robot’s servers. That means
once the robot connection is established, instructions given to the ArRobot
instance are reflected in the robot and the feedback or state of the robot is
reflected as data in certain functions of the ArRobot class. It is for this
reason that ArRobot is called the heart of ARIA because it acts as the cli-
ent–server communications gateway and the central point for collection of
state-reflection information such as position (x, y), velocity (translation and
rotation), and heading/direction.
Furthermore, ArRobot also performs the important task of managing
the program clockcycles and control of multithreading. ArRobot locks
the clock cycle with the robot information packet cycle and performs syn-
86 5 Robot Programming Packages
chronous tasks such as the Server Information Packet (SIP) handler, sensor
interpreters, action handlers, state reflectors, user tasks and many more.
The state reflector functions are listed below. These enable the program
to obtain the instantaneous state of the robot in terms of its position, veloc-
ity, heading, etc.
void ArRobot::addRangeDevice(ArRangeDevice
*device);
It is to be noted that sonar are integrated with the robot controller and that
their readings automatically come included with the standard Server In-
formation Packet (SIP) and so are handled by the standard ArRobot
packet handler. Nonetheless, we must explicitly add the sonar RangeDe-
vice with the robot object so that we can use the sonar readings for con-
trol tasks. Each RangeDevice has two sets of buffers (ArRange-
Buffer): current and cumulative, and each support two different reading
formats: box and polar
The function prototypes for both types of buffers for both the formats
are as shown:
In polar functions the return value is the nearest range within the sector
formed between the startAngle and endAngle in the counterclock-
wise direction. In Box functions the return value is the nearest range in
the rectangular box formed by the coordinates x1,y1 and x2,y2. The
parameter angle is a pointer to a double value which gives the angle to the
88 5 Robot Programming Packages
shortest range that the function returns. The current buffer contains the
most recent reading; the cumulative buffer contains several readings over
time. As stated earlier, the sonar readings are included in the SIP and can
therefore be obtained using ArRobot. The function prototypes are as
follows:
The former returns the closest range returned by the sonar numbered by
the parameter num while the latter returns a pointer to a ArSen-
sorReading object for the sonar numbered num.
The ARIA client drives the robot and runs its various accessories through
Direct and Motion commands, as well as through Actions.
Direct commands: At the very lowest level, one may send commands di-
rectly to the robot server through ArRobot. These commands are de-
fined by the robot’s operating system and consist of a 1-byte command
number followed by none or more arguments. Direct commands to the ro-
bot come in five flavors, each defined by its command argument type and
length:
ArRobot::com (unsigned char command)
Sends the command number without any arguments.
The instruction
sends the command number with a character array and its size as argu-
ments. For details refer to the ARIA User Manual.
void ArRobot::stop();
The following functions check whether the previous motion command has
been completed:
pected consequences. For this purpose Direct motion commands are exe-
cuted prior to Actions by giving them a precedence time using the function
void ArRobot::setDirectMotionPrecedenceTime (unsigned
int time)
If the time is set to 0 then a call to the function void ArRo-
bot::clearDirectMotion() should be used to cancel the overriding
effect of a Motion command so that Actions are able to regain control over
the robot.
Actions: Actions are synchronously running threads which control the mo-
bility of the robot and its accessories. As they run synchronously with the
robots clock cycle, they can run in coordination with the instantaneous
SIPs which contain essential parameters which can be used to modulate the
movement of the robot. Actions are therefore useful to impart behavior to
the robot which characterizes a number of robotic tasks
Hence, instesd of using Direct or Motion commands, it is preferable that
the ARIA client software uses Actions to drive the robot. ARIA provides
some predefined builtin Actions, all of which derive from the base class
ArAction. These include ArActionAvoidFront, ArAc-
tionAvoidSide, ArActionBumpers, ArActionConstantVe-
locity, ArActionStallRecover, ArActionGoto, and many oth-
ers. One may create an Action with desired properties by inheriting a class
from the base class ArAction. ArAction defines a member function
fire() which entirely specifies the nature of the Action.
/*
Sets the myRobot pointer (all setRobot overloaded func-
tions must do this), finds the sonar device from the
robot, and if the sonar isn't there, then it deacti-
vates itself.
*/
void ActionSonar::setRobot(ArRobot *robot)
92 5 Robot Programming Packages
{
myRobot = robot;
mySonar = myRobot->findRangeDevice("sonar");
if (mySonar == NULL)
deactivate();
}
//This fire is the whole point of the action.
if (range>0)
{
printf("Range = %.2f and angle = %.2f ",range,angle);
}
if ((angle>=0.0)&&(angle<20.0)) printf("Left 1");
else if ((angle>=20.0)&&(angle<40.0)) printf("Left 2");
else if ((angle>=40.0)&&(angle<60.0)) printf("Left 3");
else if ((angle>=-20.0)&&(angle<0.0)) printf("Right
1");
else if ((angle>=-40.0)&&(angle<-20.0)) printf("Right
2");
else if ((angle>=-60.0)&&(angle<-40.0)) printf("Right
3");
5.3 ARIA 93
ArSensorReading* r=myRobot->getSonarReading(0);
printf("(%.2f,%.2f)%.2f.\n",r->getX(),r->getY(),r-
>getSensorTh());
return &myDesired;
}
int main(void)
{
// The connection is used to talk to the robot
ArSerialConnection con;
// the robot is defined
ArRobot robot;
// the sonar device is defined
ArSonarDevice sonar;
{
printf("Could not connect to robot... exiting\n");
Aria::shutdown();
return 1;
}
// enable the motors, disable amigobot sounds
[Link](ArCommands::ENABLE, 0);
[Link](ArCommands::SOUNDTOG, 0);
[Link](&asonar, 50);
Colbert has two processes, namely finite state automata (FSA) and con-
current processes. A program in Colbert is an activity whose semantics are
based on FSA. Activity controls the overall behavior of the robot in several
ways, such as
The server: The server is the program running on the robot and it offers
all services to a client. Usually these may be instantaneous robot parame-
ters, environment characteristics such as sonar readings, images from the
camera, etc., depending on the application. Server programs have been de-
veloped in C++, with the strong support of available libraries for conven-
ience of coding.
The client: The client program, written in JAVA, runs on a local machine
and it sends requests or commands to the server either to execute a routine
or to procure data as mentioned earlier.
The socket-programming concept has been used in the design of the cli-
ent–server architecture. A socket is a logical reference to hardware or a
software port on to which programs can write or read data. Such a socket is
wrapped with formatting functions for the purpose of communicating for-
matted data instead of binary data. A server creates a socket and listens,
i.e. it waits till a client requests connections. On reception of a request, it
accepts the client by acknowledging the client connection.
One may read and write data through the socket using the following func-
tions :
Parameters:
buff buffer to read into
len how many bytes to read
msWait if 0, don't block, if > 0 wait this
long for data
Returns: number of bytes read
5.5.1 Functions
void bsInit(void)
designed in such a way that when one restarts a client program, the pro-
gram will start in a known state without any ambiguities created due to
contexts defined by other programs.
Note that if the function is called while there is no playing or synthesis go-
ing on the function will return immediately, but if synthesis or playing is
occurring it will pause before returning (until at least some of the previous
synthesis is done).
void bsFinishSpeaking(void)
This function waits until the previous speech synthesis is completed i.e.
this function will return when BotSpeak has finished with the previous
bsSpeak() or bsPlay() (bsPlay() is called for playing an au-
dio file). The following program illustrates how to use BotSpeak in a C++
program for speech synthesis.
100 5 Robot Programming Packages
//[Link]
//BotSpeak sample program
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
extern "C"{
#include "BotSpeak.h"
}
int main(int argc, char **argv)
{
char text[121];
// initialize botspeak, if the server isn't run-
ning this starts it
bsInit();
// say something so people know we're alive
bsSpeak("Type any sequence of words and I shall
say it.");
bsFinishSpeaking();
while(1)
{
printf("Enter text:-");
fgets(text,120,stdin);
printf("saying: %s",text);
bsSpeak(text);
bsFinishSpeaking();
if (strcmp(text,"exit\n")==0) break;
}
return(0);
}
board or boards in the PC digitizes the video streams into main memory. The
SVS functions are then invoked, given a stereo pair as an argument. These
functions compute a disparity image, which the user can display or process
further. The SVS provides library functions for C that are defined under
svs.h. However for C++ programmers built-in classes are available for
ease of use under svsclasses.h. We will briefly discuss the classes that
are available for image capture and processing in C++.
There are three main classes for SVS: classes that encapsulate stereo im-
ages, classes that produce the images from video or file sources, and
classes that operate on stereo images to create disparity and 3D images.
These classes are declared in the header file src/svsclass.h. The
basic idea is to have one class (svsStereoImage) for stereo images and
the resultant disparity images, which performs all necessary storage alloca-
tion and insulates the user from having to worry about these issues. Stereo
image objects are produced from video sources, stored image files, or
memory buffers by the svsAcquireImages classes, which are also re-
sponsible for rectifying the images according to parameters produced by
the calibration routines. Disparity images and 3D point clouds are pro-
duced by the stereo processing class svsStereoProcess acting on a
stereo image object, with the results stored back in the stereo image object.
The basic operations are:
1. Make a video source object and open it. Which video source is used
depends on which framegrabber interface file has been loaded.
2. Open the video source.
3. Set the frame size and any other video parameters you wish, and read
in rectification parameters from a file.
4. Start the video acquisition.
5. Loop:
The different classes that are defined under svsclasses.h are elabo-
rated as follow.
102 5 Robot Programming Packages
The stereo image class encapsulates information and data for a single ste-
reo image pair, along with any of its processed results, e.g., disparity im-
age or 3D point cloud. Stereo image objects are usually produced by one
of the image acquisition classes (svsVideoImages or
svsFileImages), then processed further by an svsStereoProcess
object. An svsStereoImage object holds information about its own
state. For instance, there are Boolean flags to tell if there is a valid set of
5.6 Small Vision System (SVS) 103
stereo images, whether they are rectified or not, if a valid disparity image
has been computed, and so on. The svsStereoImage class handles all nec-
essary allocation of buffer space for images. User programs can access the
image buffers, but should be careful not to de-allocate them or destroy
them
Constructor and destructor for the class. The constructor initializes most
image parameters to default values, and sets all image data to NULL.
char error[256];
If a member function fails (e.g. if ReadFromFile returns false), then the er-
ror will usually contain an error message that can be printed or displayed.
These members describe the stereo images present in the object. If stereo
images are present, haveImages is true. The stereo images are always
monochrome images, 8 bits per pixel. Additionally, there may be a color
image, corresponding to the left image, if requested. Color images are in
RGBX format (32 bits per pixel, first byte red, second green, third blue,
and fourth undefined). If the left color image is present, haveColor is
true. The color image isn’t used by the stereo algorithms, but can be used
104 5 Robot Programming Packages
Rectification Information
bool isRectified;//whether the rectification has
been done already
bool haveRect;//true if the rectification params
exist
svsRectParams rp;//rectification params, if they
exist
The images contained in a stereo image object (left, right and left-color)
can be rectified, that is, corrected for intra-image (lens distortions) and in-
ter-image (spatial offset) imperfections. If the images are rectified, then the
variable isRectified will be true. Rectification takes place in the
svsAcquireImage classes, which can produce rectified images using
the rectification parameters. The rectification parameters can be carried
along with the stereo image object, where they are useful in further proc-
essing, for example, in converting disparity images into a 3D point cloud.
If rectification parameters are present, the haveRect variable is true. The
rectification parameters themselves are in the rp variable.
Disparity Image
bool haveDisparity; // whether the disparity image
has been calculated yet
svsDisparityParams dp; // disparity image parame-
ters
short *Disparity(); // returns the disparity image
that a disparity pixel at X,Y of the disparity image corresponds to the X,Y
pixel of the left input image. Values –1 and –2 indicate the absence of any
disparity information: –1 for low-texture areas, and –2 for disparities that
fail the left/right check. If the disparity image has been calculated and is
present, then haveDisparity is true. The parameters used to compute
the disparity image (number of disparities, horopter offset, and so on)
are in the parameter variable dp. The disparity image can be retrieved us-
ing the Disparity function. This function returns a pointer to the dis-
parity array, so it is very efficient. User programs should not delete this ar-
ray, since the stereo object manages it.
3D Point Array
bool have3D;// whether 3D information is available
int numPoints;// number of points actually found
float *X(), *Y(), *Z();// 3D point arrays
The 3D point arrays are the 3D points that correspond to each pixel in the
left input image. It has the same size (width and height) as the input stereo
images. The 3D point array is computed from the disparity image using the
external camera calibration parameters stored in rp. An svsStereo-
Process object must be used to compute it. Each point is represented by
a coordinate (X, Y, Z) in a frame centered on the left camera focal point.
The Z-dimension is the distance from the point perpendicular to the camera
plane, and is always positive for valid disparity values. The X-axis is hori-
zontal and the positive direction is to the right of the center of the image;
the Y-axis is vertical and the positive direction is down relative to the cen-
ter of the image (a right-handed coordinate system). Negative values of Z
are used to indicate there was no valid disparity reading at a pixel. If the
3D array is present, then have3D is true. The actual number of 3D points
present in the arrays is given by numPoints.
File I/O
bool SaveToFile(char *basename); // saves images
and params to files
bool ReadFromFile(char *basename); // gets images
and params from files
bool ReadParams(char *name); // reads just params
from file
bool SaveParams(char *name); // save just params
to file
106 5 Robot Programming Packages
Just the parameters can be read from and written to a parameter file, using
ReadParams and SaveParams.
The list of acquisition classes that are used to get stereo image data are as
follows:
Acquisition classes are used to get stereo image data from video or file
sources, and put into svsStereoImage structures for further process-
ing. During acquisition, images can be rectified, that is, put into a standard
form with distortions removed. Rectification takes place automatically if
the calibration parameters have been loaded into the acquisition class. The
two subclasses acquire images from different sources. svsVideoI-
mages uses the capture functions to acquire images from a video device
such as the MEGA-D stereo head. svsFileImages acquires images
from BMP files stored on disk.
These functions are usually not called by themselves, but are implicitly
called by the constructors for the subclasses svsVideoImages and
svsFileImages.
Rectification
bool HaveRect();
bool SetRect(bool on);
bool GetRect();
bool IsRect();
bool ReadParams(char *name);
bool SaveParams(char *name);
An acquisition object acquires stereo images and returns them when re-
quested. These functions control the image streaming process. Check-
Params() determines if the current acquisition parameters are consistent,
and returns true if so. This function is used in video acquisition, to deter-
mine if the video device supports the modes that have been set. Start()
starts the acquisition streaming process. At this point, images are streamed
into the object, and can be retrieved by calling GetImage(). GetI-
mage() wait upto 30 milliseconds for a new image before it returns; if no
108 5 Robot Programming Packages
Error String
char *Error()
Call this function to get a string describing the latest error on the acquisi-
tion object. For instance, if video streaming could not be started, Error()
will contain a description of the problem
Video Acquisition
The video acquisition classes are subclasses of svsAcquireImages.
The general class is svsVideoImages, which is referenced by user
programs. This class adds parameters and functions that are particular to
controlling a video device, e.g., frame size, color mode, exposure, and so
on. Particular types of framegrabbers and stereo heads have their
own subclasses of svsVideoImages. In general, the user programs
won’t be aware of these subclasses, instead treating them as a general
svsVideoImage object. To access the svsVideoImages object, the
special function svsGetVideoObject() will return an appropriate
object.
Video Object
svsVideoImages *svsGetVideoObject()
Returns a video acquisition object suitable for streaming video from a ste-
reo device. The particular video object that is accessed depends on the
video interface library that has been loaded. This function creates a new
video object on each call; so several devices can be accessed simultane-
ously, if the hardware supports it.
5.6 Small Vision System (SVS) 109
The device must be opened before capturing the images by the stereo de-
vice. The Open() call opens the device, returning true if the device is
available. An optional name can be given to distinguish among several ex-
isting devices. The naming conventions for devices depend on the type of
device; typically it is a serial number or other identifier. These identifiers
are returned by the Enumerate() call.
Alternatively, a number can be used, giving the device in the order re-
turned by the Enumerate() function, i.e. 1 is the first device, 2 is the
second, and so on. A value of 0 indicates any available device. Upon open-
ing, the device characteristics are set to default values. To set values from
a parameter file, use the ReadParams() function. A stereo device is
closed and released by the Close() call.
These functions control the frame size and sampling mode of the acquired
image. SetSize(w,h) sets the width and height of the image returned by the
stereo device. In most cases, this is the full frame of the image. For in-
stance, most analog frame grabbers perform hardware scaling, so that al-
most any size image can be requested, and the hardware scales the video
information from the imager to fit that size. In most analog frame grabbers,
the sampling parameters (decimation and binning) are not used, and a full-
frame image is always returned, at a size given by the SetSize() func-
tion. Some stereo devices, such as the MEGA-D, allow the user to specify
a subwindow within the image frame. The subwindow is given by a com-
bination of sampling mode and window size. The sampling mode can be
specified by SetSample(), which sets binning and decimation for the
imager. The MEGA-D supports sub-sampling the image at every 1, 2 or 4
pixels; it also supports binning (averaging) of 1 or 2 (a 2 × 2 square of pix-
els is averaged). For example, with binning = 2 and decimation = 2, the
110 5 Robot Programming Packages
full frame size is 320 × 240 pixels. Using SetSize(), a smaller sub-
window can be returned. The offset of the subwindow within the full frame
comes from the SetOffset() function, which specifies the upper left
corner of the subwindow, as well as a vergence between the left and right
images. SetColor() turns color on the left image on or off. Addition-
ally, some applications require color from the right imager also, and setting
the second argument to true will return a color image for the right imager.
Generally, returning color requires more bus bandwidth and processing, so
use color only if necessary.
The video frame parameters can be set independently, and not all com-
binations of values are legal. The CheckParams() function returns true
if the current parameters are consistent. None of the frame or sampling
mode parameters can be changed while images are being acquired, except
for the offset parameters. These can be changed at any time, to pan and tilt
the subwindow during acquisition.
These functions set various video controls for the quality of the image, in-
cluding color information, exposure and gain, brightness and contrast. Not
all stereo devices support all of the various video modes described by these
parameters. In general, parameters are normalized to be integers in the
range [0,100]. SetExposure() sets the exposure and gain levels for the
device. If auto is chosen, the manual parameters are ignored. SetBal-
ance() sets the color balance for the device. Manual parameters for red
and blue differential gains are between –40 and 40. If auto is chosen, the
manual parameters are ignored. SetLevel() sets the brightness and
contrast for the device. In auto mode, the brightness value is ignored. Con-
trast is always set manually. These functions can be called during video
streaming, and their effect is immediate. The following program illustrates
how to obtain an image and store it in a file.
// [Link]
#include<stdio.h>
#include<stdlib.h>
5.6 Small Vision System (SVS) 111
#include<string.h>
#include<math.h>
#include<string>
#include"svsclass.h"
#define H 240
#define W 320
videoObject->Start();
for(int i=0;i<5;i++) imageObject = videoObject-
>GetImage(400);
if (imageObject != NULL)
{ sprintf(filename,"/home/images/%s",name);
if(imageObject->haveImages)
{
memcpy(color_image,imageObject->color,4*W*H);
imageObject->SaveToFile(filename);sendImage();
}
videoObject->Stop();
}
printf("Done , exiting\n");
videoObject->Close();
imageObject->Close();
// shutdown
Aria::shutdown();
return(0);
}
/*
For Compilation and Linking
g++ -c -I$SVS/src [Link]
g++ -o imagesave -L$SVS/bin -ldl -lcap -lsvs -pthread
sampler.o
*/
5.7 Multithreading
5.9 Summary
This chapter gives essential ingredients for readers to develop the various
application programs on robots using ARIA libraries.
6 Robot Parameter Display
6.1 Introduction
The client and server flow charts are given in Figs. 6.1 and 6.2. The server
runs on the onboard computer where robot parameters are available and
the client displays these parameters in a program window. The sample
program given in Listing 6.1 illustrates the server program written in C++
and Listing 6.2 illustrates the client program written in JAVA. The pro-
gram log session and output are shown in Fig. 6.3.
116 6 Robot Parameter Display
Start
No
End
Start
Is client Yes
connected
No
End
//filename : [Link]
#include "Aria.h"
#include <string>
int main()
{
ArSerialConnection con;
ArRobot robot;
Aria::init(Aria::SIGHANDLE_THREAD);
if ([Link]() != 0)
{
printf("Could not open the connection");
exit(1);
}
[Link](&con);
if (![Link]())
{
printf("\n Could not connect to robot");
Aria::shutdown();
exit(1);
}
[Link](true);
char fixeddata[100];
sprintf(fixeddata,"%s|%s|%.0lf|%.0lf|%.0lf|%.0lf",
robname.c_str(),robtype.c_str(),[Link](),
[Link](),[Link](),
[Link]());
[Link](fixeddata,strlen(fixeddata));
[Link](buff,sizeof(buff));
do{
char datastring[100];
[Link]();
int a;
sprintf(datastring,"%.0lf|%.0lf|%.0lf|%.0lf|%.0lf|%.0lf
|%.1lf|",
[Link](),[Link](),[Link](),[Link](),
[Link](),[Link](),
[Link]());
6.2 Flow Chart and Source Code for Robot Parameter Display 119
[Link]();
if((a=[Link](datastring, strlen(datastring)))
== strlen(datastring))
{}
else
{
printf("Error in sending hello string to the client
%d\n",a);
return(-1);
}
// Uninitialize Aria
Aria::uninit();
Aria::shutdown();
// All done
return(0);
}
120 6 Robot Parameter Display
Compilation and execution: The following line is used for the compila-
tion and execution of the server program in LINUX.
Label robname,robtype,maxvel,maxrvel,vel,rvel,lvel,
robradius,robdiagonal,batv,posx,posy,head;
public Params()
{
// set the title of the frame here.
setTitle(“Robot Parameters”);
Container cp = getContentPane();
[Link](new FlowLayout());
//position y
Box mainbox = new Box(BoxLayout.Y_AXIS);
Box sub[]= new Box[12];
for(int i = 0;i<12;i++)
sub[i] = new Box(BoxLayout.X_AXIS);
// for velocity
vel = new Label(“0”);
sub[6].add(new Label(“Robot Velocity:”));
sub[6].add([Link]());
sub[6].add(vel);
//for position x
posx = new Label(“0,0”);
sub[10].add(new Label(“Position(X,Y):”));
sub[10].add([Link]());
sub[10].add(posx);
// for heading
head = new Label(“0”);
sub[11].add(new Label(“Heading:”));
sub[11].add([Link]());
sub[11].add(head);
for(int i= 0;i<12;i++)
[Link](sub[i]);
[Link](mainbox);
addWindowListener(new WindowAdapter()
{
public void windowClosing(WindowEvent e)
{
[Link](0);
}
});
synchronized(dis)
{
n=[Link](b);
}
input = new String(b,0,n);
[Link](n+”Server:”+input);
[Link](500);
[Link]((new String(“recd”)).getBytes());
[Link]();
6.2 Flow Chart and Source Code for Robot Parameter Display 123
[Link]([Link]()+”,”+
[Link]());
[Link]([Link]());
[Link]([Link]());
[Link]([Link]());
[Link]([Link]());
[Link]([Link]());
invalidate();
validate();
}while(input!=null);
[Link]();
[Link]();
}
catch(Exception ex)
{
[Link]();
}
}
}
public static void main(String arg[])
{
Params p =new Params();
try
{
Thread t = new Thread(p);
[Link]();
}
catch(Exception e){}
}
}
Syncing 0
Syncing 1
Syncing 2
Connected to robot.
Name: arcane
Type: Pioneer
Subtype: p2de
Loaded robot parameters from p2de.p
6.3 Summary 125
6.3 Summary
This chapter highlights the flow chart and the program code to display
various parameters of the robot which helps writing programs for real time
applications. Fig. 6.3 displays the JAVA Frame that contains the robot pa-
rameters, such as the name of the robot (“arcane”) and its type (“Pioneer”).
The robot has a maximum translational velocity of 2200 mm/sec and the
maximum rotational velocity is 500 mm/sec. Similarly, the robot’s coordi-
nates are currently (−712 mm, 408 mm) with respect to the starting point.
The robot’s battery voltage is 11.9 volts, while its heading is 115°. When-
ever these parameters change they are reflected in the JAVA frame run-
ning on the client machine.
7 Program for BotSpeak
7.1 Introduction
The client and server flow charts used for the BotSpeak program are
illustrated in Figs. 7.1 and 7.2 and their sample programs written in
C++ and Java are shown in Listing 7.1 and Listing 7.2 respectively.
The BotSpeak program output with program log session is depicted in
Fig. 7.3.
128 7 Program for BotSpeak
Start
Yes
Is Client Con-
nected
No
End
Start
Yes
Is Client
Connected
No
End
// filename : [Link]
#include<iostream.h>
#include<string.h>
#include"Aria.h"
// for including the Botspeak.h for C
extern "C" {
#include"BotSpeak.h"
}
main()
{
// the Aria client and server socket.
ArSocket server,client;
[Link](&scon);
while(true)
{
// reading the string from the client.
size = [Link](str,sizeof(str));
if ( size > 0)
{
str[size] = '\0';
printf("\n Client said :: %s %d
%d",str,strlen(str),size );
bsSpeak(str);
bsFinishSpeaking();
if(!strcmp(str,"Disconnect"))
{
printf("Disconnecting from the client.");
break;
}
}
}
Compiling and execution: The following text is used for the compilation
and execution of the program
container = [Link]();
[Link](null);
addWindowListener(new WindowEventHandler());
setDefaultCloseOpera-
tion(WindowConstants.DISPOSE_ON_CLOSE)
setSize(400,350); /// set the size of the frame
show();
}
return str;
}
catch(IOException e)
{
[Link](e);
}
}
[Link]("");
[Link]("");
[Link]();
}
}
// the main function.
public static void main(String[] args)
{
BotSpeak frame = new BotSpeak("BotSpeak");
}
}
Syncing 0
Attempting to close previous connection.
Syncing 0
Syncing 1
Syncing 2
Connected to robot.
Name: arcane
Type: Pioneer
Subtype: p2de
Loaded robot parameters from p2de.p
7.3 Summary
The chapter highlights the usefulness of the BotSpeak program. Fig. 7.3
shows the JAVA Frame consisting of a text box and a “Clear” button. The
robot pronounces the text written in the text field. The IP address of the
server, i.e. [Link] is displayed at the bottom right-hand side of the
display window.
8 Gripper Control Program
8.1 Introduction
The client and server flow charts used for the gripper control program are
illustrated in the Figs. 8.1 and 8.2 and their sample programs written in
C++ and JAVA are shown in Listing 8.1 and Listing 8.2 respectively. The
gripper control program output with program log session is depicted in
Fig. 8.3.
138 8 Gripper Control Program
Start
Is Beam bro- No
ken?
Yes
No
End
Start
Is Client Yes
Connected?
No
End
#include"Aria.h"
#include<stdlib.h>
#include<signal.h>
ArSocket server,client;
{
printf("\n Closing the connection");
[Link]();
[Link]();
Aria::shutdown();
exit(0);
}
main()
{
// used for adding ctrl+c handler
struct sigaction sa;
memset(&sa,0,sizeof(sa));
sa.sa_handler = &shutdown;
sigaction(SIGINT,&sa,NULL);
char str[100];
[Link](&scon);
while(true)
{
// read the instruction from the client
size = [Link](str,sizeof(str));
if ( size > 0)
{
str[size] = '\0';
[Link]();
{
[Link]();
ArUtil::sleep(50);
}
JLabel cLabel;
char mnemonics[] = {'O','C','U','D','G','L','S','R'};
int bWidth = 120;
int bHeight = 25;
container = [Link]();
[Link](null);
{
JButton b = new JButton(str[i]);
[Link](loc[i][0],loc[i][1],bWidth,bHeight);
[Link](mnemonics[i]);
[Link](b);
[Link](this);
}
addWindowListener(new WindowEventHandler());
setDefaultCloseOpera-
tion(WindowConstants.DISPOSE_ON_CLOSE)
setSize(400,350); //set the size of the frame
show();
if([Link]("1")||[Link]("2")||[Link]
s("3"))
{
writeString(output,"Close");
string = "0";
}
else
{
// do nothing
if ([Link](""))
{
writeString(output,"Hello");
}
else
{
writeString(output,string1);
[Link](string1);
string1 = "";
}
}
string = getString(input);
[Link](string);
[Link]();
}
}
catch(IOException e){}
}
// destructor function
void finalise()
{
try
{
[Link]();
}
catch(IOException e)
{
[Link](e);
}
}
pos = [Link](buf);
if(pos<=0) return null;
String str = new String(buf,0,pos);
return str;
}
if ([Link]("0"))
{
[Link](50,50,300,10); // inner beam
[Link](50,100,300,10);//outer beam
}
if([Link]("1"))
{
[Link](50,50,140,10); // inner beam broken
[Link](210,50,140,10);//inner beam broken
[Link](50,100,300,10);//outer beam
}
if([Link]("2"))
8.2 Flow Chart and Source Code for Gripper Control Program 149
{
[Link](50,50,300,10); // inner beam
[Link](50,100,140,10); //outer beam broken
[Link](210,100,140,10); //outer beam broken
}
if([Link]("3"))
{
[Link](50,50,140,10); // inner beam broken
[Link](210,50,140,10); // inner beam broken
[Link](50,100,140,10); //outer beam broken
[Link](210,100,140,10); // outer beam broken
}
}
}
}
Syncing 0
Syncing 1
Syncing 2
Connected to robot.
Name: arcane
Type: Pioneer
Subtype: p2de
Loaded robot parameters from p2de.p
8.3 Summary
In this chapter the concept of gripper control is explained with the related
programs, which is useful in real-time applications. There are two beams
in the gripper, one at the outer end of the gripper while the other is at the
opposite extreme, i.e. inner end. When they break it means that there is
some obstacle between the grippers, and the gripper takes action to close
it. If any beam is broken it is shown as a broken beam in the output JAVA
Frame as in Fig. 8.3. As shown there are eight buttons. When any one of
them is clicked then the client receives the user request. This information
is forwarded to the server where the corresponding subroutine program
runs. When “Grip Open” is pressed, it opens the gripper. If “Grip Close” is
pressed then the gripper will be closed. If “Grip Stop” is pressed, then the
moving gripper will be stopped and the same process is carried out for lift-
ing the gripper. The function of “Ready” keeps the gripper in the ready po-
sition i.e. ready to grab any object laying in front it. The “Store” key keeps
the gripper in store position. The break in the outer beam shown in the Fig.
8.3 is due to the presence of an obstacle between the gripper arms.
9 Program for Sonar Reading Display
9.1 Introduction
The client and server flow charts used for the sonar display program are il-
lustrated in Figs. 9.1 and 9.2 and their sample programs written in C++ and
Java are shown in Listing 9.1 and Listing 9.2 respectively. The program
output with program log session is depicted in Fig. 9.3.
152 9 Program for Sonar Reading Display
Start
No
End
Start
No
End
// filename : [Link]
#include"Aria.h"
#include<stdlib.h>
#include<string.h>
#include<signal.h>
ArSocket server,client;
// for ctrl+c
void shutdown(int signum)
{
printf("\n Closing the connection");
[Link]();
[Link]();
Aria::shutdown();
exit(0);
}
main()
{
// for ctrl + C handler
struct sigaction sa;
memset(&sa,0,sizeof(sa));
sa.sa_handler = &shutdown;
sigaction(SIGINT,&sa,NULL);
size_t size;
str[0] = '\0';
[Link]();
[Link]();
Aria::shutdown();
return 0;
}
// filename : [Link]
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
public class Sonar extends JFrame
156 9 Program for Sonar Reading Display
{
Container container=null;
boolean flag =true;
Socket socket;
InputStream input; OutputStream output;
JLbl lbl;
double s_r[] = new double[16];
{
[Link](e);
}
addWindowListener(new WindowEventHandler());
setDefaultCloseOpera-
tion(WindowConstants.DISPOSE_ON_CLOSE)
setSize(330,380);
show();
try
{
while(true)
{
for (int i = 0 ; i < 16 ; i++ )
{
if (flag)
{// sending the ack. Signal here
writeString(output,"Hello");
str = getString(input);
s_r[i] = (double)[Link](str);
}
}
[Link]();
}
}
catch(IOException e){}
}
// the destructor
void finalise()
{
try
{
[Link]();
}
catch(IOException e)
{
[Link](e);
}
}
{
int c, pos =0;
byte buf[]= new byte[1024];
pos = [Link](buf);
if(pos<=0) return null;
String str = new String(buf,0,pos);
return str;
}
public JLbl()
{
s_max = 5000.0;
for ( int i = 0 ; i < 16 ; i ++ )
s_r[i] = s_max;
}
// for 16 sonars
for ( int i = 0 ; i < 16 ; i++ )
{
if ( s_r[i] > s_max )
s_r[i] = s_max;
if (x > 0) x += d/2;
else x -= d/2;
if ( y > 0) y += d/2;
else y -= d/2;
int x1,y1;
if (x > 0) x1 = (int)(x+0.5);
else x1 =(int)(x-0.5);
if (y > 0) y1 = (int)(y+0.5);
else y1 =(int)(y-0.5);
[Link]([Link]);
[Link](cx+x1-2,cy-y1-2,cx+x1+2,cy-y1+2);
[Link](cx+x1+2,cy-y1-2,cx+x1-2,cy-y1+2);
}
//function for getting the width of the label
public int getIconWidth(){return width;}
//function for getting the height of the label
public int getIconHeight(){return height;}
}
}
9.3 Summary
In this chapter the program for the sonar reading display has been discussed.
It can be seen from Fig. 9.3, that there are 16 crosses in total in the figure.
Each of these crosses represents a sonar reading. The robot is shown at the
center of the frame. There is an outer circle, which shows the upper limit of
sonar readings. The sonar readings shown in the figure represent the actual
sonar positions of the robot. The label at the bottom right side shows that the
client is connected to the server. This program will be helpful for the devel-
opment of various application programs for mobile robots to avoid obstacle
collision. We will discuss such a program in the next chapter, i.e. wandering
with obstacle avoidance by using the sonar readings.
10 Program for Wandering Within the Workspace
10.1 Introduction
The server algorithm implements the actions on the robot when the signal
“Start” comes from the client. The client algorithm takes the instructions
from the user regarding starting/stopping the wander mode. The client and
server flow charts used for wandering in the workspace are illustrated in
the Figs. 10.1 and 10.2 and their sample programs written in C++ and Java
are shown in Listing 10.1 and Listing 10.2 respectively. The program out-
put with program log session is depicted in Fig. 10.3.
164 10 Program for Wandering Within the Workspace
Start
If No
X = Start
Yes Remove actions
Add all actions And Send (x,y,th)
And send (x,y,th)
Is Client
Connected Yes
No
End
Start
Is Client Yes
Connected
No
End
// for ctrl+c
void shutdown(int signum)
{
printf("\n Closing the connection");
[Link]();[Link]();
Aria::shutdown();
exit(0);
}
// the main
main()
{
// the ctrl+c handler
struct sigaction sa;
memset(&sa,0,sizeof(sa));
sa.sa_handler = &shutdown;
sigaction(SIGINT,&sa,NULL);
// the actions
ArActionStallRecover recover;
ArActionBumpers bumpers;
ArActionAvoidFront avoidFrontNear("Avoid Front Near",
275, 0);
ArActionAvoidFront avoidFrontFar;
ArActionConstantVelocity constantVelocity("Constant Ve-
locity", 250);
while(true)
{
char str[20];
str[size]='\0';
[Link](&recover, 100);
[Link](&bumpers, 75);
[Link](&avoidFrontNear, 50);
[Link](&avoidFrontFar, 49);
[Link](&constantVelocity, 25);
[Link]();
}
sprintf(str,"%d|%d|%d|",(int)[Link](),
(int)[Link](),(int)[Link]());
try
{
while(true)
{
// getting the (x,[Link]) here
for ( int i = 0 ; i < 3 ; i++ )
{
writeString(output,"Hello");
170 10 Program for Wandering Within the Workspace
str = getString(input);
z[i] = (double)[Link](str);
}
[Link]("X :: "+x1);
[Link]("Y :: "+y1);
[Link]("Th :: "+th1);
[Link](x1,y1,th1);
// when values change repaint the label.
[Link]();
}
}
catch(IOException err){}
}
// destructor
void finalise()
{
try
{
[Link]();
}
catch(IOException e)
{
[Link](e);
}
}
// function for getting the string/data from socket
private String getString(InputStream in) throws IOEx-
ception
{
int c; int pos =0;
byte buf[]= new byte[1024];
pos = [Link](buf);
if(pos<=0) return null;
String str = new String(buf,0,pos);
return str;
}
[Link]([Link]());
}
// the robot
[Link](cx-d/2,cy-d/2,d,d);
int x1 = (int)(d*[Link]([Link](th))/2);
int y1 = (int)(d*[Link]([Link](th))/2);
172 10 Program for Wandering Within the Workspace
[Link](cx,cy,cx+x1,cy-y1);
}
// function to return width.
public int getIconWidth(){return width;}
Syncing 0
Syncing 1
Syncing 2
Connected to robot.
Name: arcane
Type: Pioneer
Subtype: p2de
Loaded robot parameters from p2de.p
10.3 Summary
As shown in Fig. 10.3, the client interface has two buttons, i.e. “Start” and
“Stop”. When one clicks the “Start” button then the robot starts running in
“Wander” mode and when the “stop” button is clicked the robot stops
wandering. The current position and heading (Th) in the figure are indi-
cated in the bottom left corner of the JAVA frame and at the right-hand
corner there is a label showing that the robot is connected to the client.
11 Program for Tele-operation
11.1 Introduction
The server algorithm is meant for collecting the commands regarding mo-
tion from the client and executing them. The client algorithm gives the in-
structions to get these commands from the user. The client and server flow
charts used for the program for tele-operation are illustrated in Figs. 11.1
and 11.2 and their sample programs written in C++ and Java are shown in
Listings 11.1 and 11.2 respectively. The program output with program log
session is depicted in Fig. 11.3.
176 11 Program for Tele-operation
Start
Is Client Yes
Connected
No
End
Fig. 11.1. Server flow chart for the program for tele-operation
Start
Is Client Yes
Connected
No
End
Fig. 11.2. Client flow chart for the program for tele-operation
11.2 Algorithm and Source Code for Tele-operation 177
// filename : [Link]
#include"Aria.h"
main()
{
// for socket
ArSocket server,client;
char str[100];
{
printf("\n Unable to open the Server Socket.");
Aria::shutdown();
return 1;
}
[Link](true);
while(true)
{
// get the instruction
size = [Link](str,sizeof(str));
if ( size > 0)
{
str[size] = '\0';
printf("\n Client said :: %s %d
%d",str,strlen(str),size );
[Link](),[Link]());
}
while(true)
{
[Link]();
if([Link]())
{
[Link]();
break;
}
[Link]();
ArUtil::sleep(50);
}
}
[Link]();
head -= rHeading;
head %= 360;
[Link](head);
[Link]();
while(true)
{
[Link]();
if([Link]())
{
[Link]();
break;
}
[Link]();
ArUtil::sleep(50);
}
}
// filename : [Link]
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
import [Link].*;
public class Teleop extends JFrame implements Ac-
tionListener
{
Container container=null;
Socket socket;
InputStream input;
OutputStream output;
String str[] = {"Move Forward","Move Back","Move
Left","Move Right"};
char mnemonics[] = {'F','B','L','R'};
int bWidth = 120; // button width
int bHeight = 25; // button height
int loc [][] =
{{70,220},{210,220},{140,190},{140,250}};
JLabel x,y,th;
int th1=0;
double x1=0.0,y1=0.0;
JLbl lbl;
public Teleop(String title)
{
super(title);
container = [Link]();
[Link](null);
}
if ([Link]()==e.VK_DOWN)
{
x1 -= 0.1*[Link](ang);
y1 -= 0.1*[Link](ang);
writeString(output,"Backward");
}
if ([Link]()==e.VK_LEFT)
{
writeString(output,"Left");
th1 += 10;
if (th1 == 360)
th1 = 0;
}
if ([Link]()==e.VK_RIGHT)
{
th1 -= 10;
if (th1 < 0)
th1 += 360;
writeString(output,"Right");
}
x1 = (int)(x1*100);
y1 = (int)(y1*100);
x1 = x1/100;
y1 = y1/100;
[Link]("X :: "+x1);
[Link]("Y :: "+y1);
[Link]("Th :: "+(th1));
[Link](x1,y1,th1);
[Link]();
}
catch( IOException err) {}
}});
[Link]();
// for x,y,th
x = new JLabel("X :: 0.0");
y = new JLabel("Y :: 0.0");
th = new JLabel("Th :: 0");
[Link](10,250,100,15);
[Link](10,265,100,15);
[Link](10,280,50,15);
[Link](x);
[Link](y);
[Link](th);
// the simulator
lbl = new JLbl();
[Link](0,0,399,170);
[Link](lbl);
if ([Link](str[0]))
{
writeString(output,"Forward");
x1 += 0.1*[Link](ang);
y1 += 0.1*[Link](ang);
}
if ([Link](str[1]))
{
x1 -= 0.1*[Link](ang);
y1 -= 0.1*[Link](ang);
writeString(output,"Backward");
}
if ([Link](str[2]))
{
writeString(output,"Left");
th1 += 10;
if (th1 == 360)
th1 = 0;
}
if ([Link](str[3]))
{
th1 -= 10;
if (th1 < 0)
th1 += 360;
writeString(output,"Right");
}
x1 = (int)(x1*100);
y1 = (int)(y1*100);
x1 = x1/100;
y1 = y1/100;
[Link]("X :: "+x1);
11.2 Algorithm and Source Code for Tele-operation 185
[Link]("Y :: "+y1);
[Link]("Th :: "+(th1));
[Link](x1,y1,th1);
[Link]();
}catch( IOException e) {}
}
pos = [Link](buf);
if(pos<=0) return null;
String str = new String(buf,0,pos);
return str;
}
{
writeString(output,"Disconnect");
}
catch(IOException exc){}
[Link](0);
}
}
// the simulator
class JLbl extends JLabel
{
public int width = 380,height= 200;
public int x=197,y=97,d=14,th=0;
public int cx=x,cy=y;
Syncing 0
Attempting to close previous connection.
Syncing 0
Syncing 1
Syncing 2
Connected to robot.
Name: arcane
Type: Pioneer
Subtype: p2de
Loaded robot parameters from p2de.p
11.3 Summary
It can be seen from Fig. 11.3 that the simulator consists of four buttons.
One can use these four buttons or the mnemonics (Alt + understrike letter).
With each action performed the robot in the simulator also moves accord-
ingly. When it crosses the boundary it is again brought back into the region
of the simulator. The current position is given by (X, Y) and the direction
by theta (Th). Using this program one can run the robot safely from a dis-
tance. Here “Direct Motion” commands are used for the tele-operation, but
instead “Actions” may be used.
12 A Complete Program for Autonomous
Navigation
12.1 Introduction
/home/
motion/
Makefile the description file for make
Server the motion server executable
Socket.h header file for Socket class
[Link] Socket class definition file
Socket.o object file generated after compilation
ServerSocket.h header file for ServerSocket
[Link] ServerSocket class definition file
ServerSocket.o object file generated after compilation
SocketException.h header file for socket exceptions
simple_server_main.cpp source code for the motion server
simple_server_main.o object file generated after compilation
vision/
trialserver Black & white and Color image server
[Link] image server source file
190 12 A Complete Program for Autonomous Navigation
CLIENT
NAVIGATOR
The image server program opens a listening socket on port 4325 of the ro-
bot’s onboard computer. On receiving a request from the navigator client,
the program opens the vision system for continuous video and by using a
simple run-length encoding algorithm [Jahne, 1997] compresses the black
and white image from the left camera and transfers the image data over the
network to the client computer. In the navigator client the image is dis-
12.2 The ImageServer Program 191
played in the upper left corner of the window. The incoming images from
the server are continuously displayed. The program encodes the black and
white image taken by the framegrabber of the server into the run-length
encoded image and transmits over the network using the socket. This pro-
gram resides in the /home/vision folder of the robot’s computer. The
source code is available in Listing 12.1 at the website of the book. Telnet
session after execution is given below:
This program controls the robot’s movements, obstacle detection and grip-
per functions. The socket communication in this program is encapsulated
in Socket and SocketServer C++ classes. These classes implement
methods for handling low-level LINUX socket communication [Mitchell,
2001]. The Socket class implements all the basic socket operations (like
bind, listen, accept, connect, write and recv) and the SocketServer class
adds the possibility of exceptions that may occur during the lifecycle of a
socket. In this section, the program opens a connection to the robot or the
robot simulator and then waits on port 4040 for a connection from the
Navigator client. On negotiating a successful connection with the naviga-
tor client, the program starts an infinite loop in which it sends the client in-
formation about the robot’s state, such as the robot’s position, heading,
translational and rotational velocity and battery voltage. The socket han-
dling the communication is set as non-blocking so that a read function on
the socket does not block the program. This is done because the data or
command sent from the client to the motion server is of an asynchronous
nature. And if the program is blocked during the read operation, the client
will not be provided with the robot’s state information. The client program
sends specific commands in the form of special strings. The program then
interprets the commands and if a match is found the associated function is
executed. The list of valid commands is given in Table 12.1. The listing of
various program codes for the robot motion server is available in Listing
12.2 at the website of the book. The Telnet session is given below.
Connected to robot.
Name: Burla_1473
Type: Pioneer
Subtype: p2de
Loaded robot parameters from p2de.p
Gripper: queried, using General IO.
• Client: This handles socket communication with the motion server and
the image server.
• Camera: This handles the reception and display of the run-length en-
coded image received from the image server.
• Map: This displays the robot’s position and range sensor information in
2D Cartesian coordinate display.
• Robot: This encapsulates the robot properties for display in the above
coordinate system.
• Navigator: This integrates all the classes and implements the user inter-
face with the program. It also receives the robot’s state information on a
separate thread.
The navigator is the main class and brings together all the functionalities
of the classes. This program spawns two threads one to receive the image
from the image server and the other for receiving the state information of
the robot. On the main thread the program listens to user events and ac-
cordingly commands the motion server. The various program codes of the
navigator is available in Listing 12.3 of the website of the book. The navi-
gator programs can be executed from the command prompt by issuing the
following commands:
C:\> cd Navigator
C:\Navigator\> set PATH=%PATH%;C:\jdk1.4\bin
C:\Navigator\> java Navigator
196 12 A Complete Program for Autonomous Navigation
The navigator program must be launched after starting both the image
server and the motion server programs. These server programs can be
launched from separate Telnet sessions with the robot’s onboard computer.
The procedural details have been discussed with the individual programs.
On launching the navigator client program, connection is established with
the image server and the motion server. The front end of the Navigator
Client program is shown in Fig. 12.2. The upper left sub-window gives a
continuous display of the run-length encoded black and white image re-
ceived from the left camera of the stereo rig. The right half of the screen
displays the bird’s-eye view of the robot along with the sonar sensor read-
ings as a red dot around the robot. Robot control functions are available in
the left lower panel. The Open, Close, Up, Down, Ready and Stop button
in the first row control the gripper of the robot. In navigator, the robot can
be operated in three different modes and these are available in the Navi-
gate drop down menu.
12.4 The Navigator Client Program 197
• Tele-operate: This is the default mode where the keyboard keys are
used to control the robot. To activate this mode one must pay attention
to the right display sub-window. This is achieved by a mouse click in
the subwindow. The following keys are used to operate the robot:
• Wander: This activates the wander activity in the robot. The Go button
is used to launch this mode and the Halt button stops it. In this mode the
robot autonomously wanders around avoiding obstacles on its own and
sends the sonar readings and video image from the left camera. This is
used to take the sensory readings of the robot.
198 12 A Complete Program for Autonomous Navigation
The text box named Speak activates the robot’s speech-synthesis system.
The text in the text box will be read aloud by the robot’s BOTSPEAK sys-
tem using the IBM VIAVOICE speech engine. The Commentary checkbox
enables or disables online commentary of the actions taken by the robot. If
the “ready” button is activated, the robot can grab and lift an object, when-
ever it finds an object between its open paddles. On the control panel,
lower left side, one can find state variable indicators such as position (x,
y), heading, velocity (translational and rotational) and battery voltage. A
bird’s-eye view of the robot’s surroundings is shown in Fig. 12.3 and the
image sequence is shown in Fig. 12.4.
12.5 Summary
13.1 Introduction
One of the limitations of machine vision is that the imaging process is in-
terpreted from the information on a 2D image relating to the 3D world. But
this can be modeled with the knowledge of the physical process of image
formation, i.e. how the 3D world scene is projected onto the image plane
of the camera giving rise to the 2D imagery. This basically constitutes the
basis of perspective projection, which will be covered later in this chapter.
It is not possible to recover the 3D spatial geometry from a single image.
However if we have multiple images of the scene at hand, taken from dif-
ferent viewing angles and positions, then it is possible to extract the 3D
geometric information by a combination of these images, which is known
as stereo-vision.
The camera projects the 3D world onto its image plane. The image
formed in the image plane of the camera is essentially 2D in nature. As
mentioned earlier, it is necessary to have at least two 2D images to inter-
pret the 3D information contained in them. But another difficulty comes in
between in merging the two images as there may be many uncertainties in-
volved in this imaging. The first one is the uncertainty regarding the posi-
tion and orientation of the various geometrical primitives in the image
planes, which give rise to uncertainty in estimation of the 3D features.
Secondly, uncertainty in camera parameters such as focal length and ran-
dom measurement errors also adds uncertainty in the measurement proc-
ess. Little relevant work has been reported in the area of 3D exploration of
the environment or 3D object reconstruction. Reconstruction of 3D fea-
tures by structured light and least squares estimation techniques have been
explained in by Haralick and Shapiro [Haralick, 1993]. Asada [Asada,
1990] has fused sensory/camera images and a sonar range scanner for re-
construction of a world map.
Reconstruction of 3D environment
Y
(r, s)
Image line
(rf/s, f)
f
Lens
ered in the next section. The point (r, s) is represented as (r, s, 1) in the
homogenous coordinate system. The first linear transformation translates
the point (r, s, 1) down the Y-axis by a distance f. The second trans-
formation takes the perspective transformation to the image line. Hence,
⎛ 1 0 0 ⎞⎛ r ⎞
⎛ ku ⎞ ⎛⎜ 1 0 0 ⎞⎜ ⎟⎜ ⎟
⎟⎜ 0 1 − f ⎟⎜ s ⎟
⎜⎜ ⎟⎟ = 1 (13.1)
⎜ 1 ⎟⎠⎜
⎝ kv ⎠ ⎝ 0 f ⎟⎜ ⎟
⎝ 0 0 1 ⎠⎝ 1⎠
With this understanding of perspective projection, let us discuss the proc-
ess of 3D perspective projection.
Model of Per-
Object Point spective Pro- Image Point
(3D world) jection Trans- (2D Image)
form
Camera Parameters
P (x, y, z)
3D object point
Fig. 13.5. Camera model of 3D projection (the global coordinate system and cam-
era coordinate systems are assumed to be the same here)
simplicity, at first the world coordinate system is taken to align with the
camera coordinate system.
In Fig. 13.5, a point having spatial coordinates (x, y, z) is mapped onto
its image I(u, v) on the image plane. Using the principle of perspective pro-
jection
x u f
= − .⇒ u = − x
z f z
y v f
= − .⇒ v = − y (13.2)
z f z
projection does not preserve distances between points, nor their ratios.
Thus if A, B, C are collinear in 3D space, then
At this point, we can put the 3D–2D transformation in a linear matrix form
given by (13.4).
⎛ ku ⎞ ⎡1 0 0 0⎤ ⎡x ⎤
⎜ ⎟ ⎢
⎜ kv ⎟ ⎢0 1 0 0⎥⎥ ⎢y⎥
⎢ ⎥
⎜ kw ⎟ = ⎢0 0 1 0⎥ ⎢z⎥
(13.4)
⎜ ⎟ ⎢ ⎥ ⎢ ⎥
⎜ k ⎟ 0 0 −1/ f 0⎦
⎝ ⎠ ⎣ ⎣1 ⎦
This is the representation of the 2D point in the image plane located at (0,
0, −f). Hence the value of w will be kw/w = z/(−z/f) = −f as verified. Now
let us try to recover the 3D object point from its coordinates in the image
plane by taking the product of the inverse of the linear transformation
matrix and the image plane coordinates. Then we will definitely arrive at
erroneous results, or ambiguity. This is because of the many-to-one trans-
formation characteristic of the perspective matrix. Knowledge of at least
one 3D coordinate is essential for reconstruction of the 3D point. If we try
to represent the image plane coordinates w.r.t. a coordinate system cen-
tered on the image plane as shown in Fig. 13.6, then it is required to trans-
late the coordinate system from the center of perspectivity to the image
plane by a distance f along the optical axis. The point will now be
210 13 Imaging Geometry
⎛1 0 0 0 ⎞⎛ x ⎞
⎛ ku ⎞ ⎛ 1 0 0 0 ⎞⎜ ⎟⎜ ⎟
⎜ ⎟ ⎜ ⎟⎜ 0 1 0 0 ⎟⎜ y ⎟
⎜ kv ⎟ = ⎜ 0 1 0 0 ⎟⎜ (13.6)
⎜ k ⎟ ⎜ 0 0 −1 f 0 0 1 f ⎟⎜ z ⎟
⎝ ⎠ ⎝ 1 ⎟⎠⎜⎜ ⎟⎜ ⎟
⎝0 0 0 1 ⎟⎠⎜⎝ 1 ⎟⎠
⎛1 0 0 0 ⎞⎛ x ⎞
⎛ ku ⎞ ⎛ 1 0 0 0 ⎞⎜ ⎟⎜ ⎟
⎜ ⎟ ⎜ ⎟⎜ 0 1 0 0 ⎟⎜ y ⎟
⎜ kv ⎟ = ⎜ 0 1 0 0 ⎟⎜ (13.7)
⎜ k ⎟ ⎜0 0 1 f 0 0 1 − f ⎟⎜ z ⎟
⎝ ⎠ ⎝ 1 ⎟⎠⎜⎜ ⎟⎜ ⎟
⎝0 0 0 1 ⎟⎠⎜⎝ 1 ⎟⎠
It has been assumed so far that the camera and the world coordinate system
coincide with each other. In this case, however, when it is required to es-
timate the 3D features w.r.t. a user selected world coordinate system, it is a
cumbersome task to take the camera system as the reference for each view
position. Hence we need to dissociate the camera and world coordinate
system, when we take several images of the 3D scene from different view-
ing position.
13.5 Global Representation 211
where  represents the global system (X, Y, Z), Â′ represents the trans-
formed global system, Âc represents the camera system (Xc Yc, Zc) and T
and R represent translation and rotation vectors.
The process of aligning two coordinate systems is discussed in the next
section.
position to position and thus it is necessary to take into account the relative
changes in the camera position at each location. Hence a user defined co-
ordinate system is used, which is also called the global system. All meas-
urements are then estimated w.r.t. the global system. This ensures conven-
ience in constructing the world/global map by fusing the multiple-image
information from several local maps. The camera coordinate system shown
in Fig. 13.7 is attached to the robot and can take multiple images of the
scene from different positions and directions.
In order to have a global representation, it is necessary to establish a re-
lationship between the maps sensed by camera, i.e. the camera coordinate
system and the global coordinate system. It is necessary to bring about a
series of transitions of the coordinate system pertaining to the correspond-
ing frames of reference. The first step is the transition of the camera-based
coordinate system to the robot coordinate system, for transforming the sen-
sor map to the virtual map. Let (xc, yc, zc), be the displacement vector of the
origin of the vehicle based coordinate system w.r.t. the camera-based co-
ordinate system. Then in the estimation, the origin of the camera-based
⎛ X 'c ⎞ ⎛ X c − x c ⎞
⎜ ⎟ ⎜ ⎟
⎜ Yc' ⎟ = ⎜ Yc − y c ⎟ (13.9)
⎜⎜ ' ⎟⎟ ⎜ ⎟
⎝ Zc ⎠ ⎝ Zc − z c ⎠
where Xc, Yc, Zc corresponds to the axes of the camera-based coordinate
system. The alignment of the two system axes after translation is shown in
Fig. 13.8.
Next the new coordinate system is aligned with the robot coordinate
system, so that a relation is established between the camera-based coordi-
nate system with the robot coordinate system, which is done by a sequence
of rotations about properly chosen axes.
Step 1: Rotation about the Zc′ axis by φ1: In this case the Xc′ – Yc′ plane
is rotated about the Zc′ axis by φ1 where φ1 is the angle between Xc′ and the
Xv– Zc′ plane measured along the Xc′ – Yc′ plane. The new coordinate sys-
tem is represented by (13.10) and shown in Fig. 13.9.
Yc′
Zv
Yv
φ1
Xc′
Zc′
Xv
Fig. 13.8. Orientation of camera axes after translation to the robot coordinate sys-
tem. Yv and Xv lie on the black plane, while Zv is perpendicular to it. Xc′ and Yc′ lie
on the white plane while Zc′ is perpendicular to it. Xc′ will be rotated to Xv– Zc′
plane
214 13 Imaging Geometry
Zv
Yv
θ1
Zc′′
Xc′′ Xv
Yc′′
Fig. 13.9. Orientation of camera axes after step 1. Yv and Xv lies on the black
plane, while Zv is perpendicular to it. Yc′′ lies on the white plane while Zc′′ and
Xc′′ are perpendicular to it. Now the Xc′′– Zc′′ plane will be rotated by an angle θ1
in order to align Xc′′ with Xv
Step 2: Rotation about the Yc′′ axis by θ1: Here the Xc′′–Zc′′ plane is ro-
′′
tated about the Yc′′ axis by an angle θ1, where θ1 is the angle between Xc
and Xv along the Xc′′–Zc′′ plane. Thus the new coordinate system is repre-
sented by (13.11) and shown in Fig. 13.10.
Zv
Yv
ψ1
Zc′′′
Yc′′′
Xc′′′= Xv
Fig. 13.10. Orientation of camera axes after step 2. Yv and Xv lie on the black
plane, while Zv is perpendicular to it. Yc′′′ lies on the white plane while Zc′′′ and
Xc′′′ are perpendicular to it. Xc′′′ is seen to be aligned with Xv. Now the Yc′′′– Zc′′′
plane will be rotated by an angle ψ1 in order to align Zc′′′ with Zv. Then the Yc′′′
will be automatically aligned with Yv
Step 3: Rotation about the Xc′′′ axis by ψ1: Here the Yc′′′–Zc′′′ plane is
rotated about the Xc′′′ axis by ψ1, where ψ1 is the angle between Zc′′′ and Zv
measured along the Yc′′′–Zc′′′ plane. Thus the new coordinate system is de-
noted by (13.12) and shown in Fig. 13.11.
⎛ X ivc ⎞ ⎛ 0 0 1 ⎞⎛ X 'c'' ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ Yciv ⎟ = ⎜ cos ψ1 sin ψ1 0 ⎟⎜ Yc''' ⎟ (13.12)
⎜⎜ iv ⎟⎟ ⎜ ⎟⎜⎜ ''' ⎟⎟
⎝ Zc ⎠ ⎝ − sin ψ1 cos ψ1 0 ⎠⎝ Zc ⎠
216 13 Imaging Geometry
Zciv= Xv
Yciv=Yv
Xciv= Xv
Fig. 13.11. Orientation of camera axes after step 3. The camera and the robot
coordinate systems are now aligned after one translation and three subsequent
rotations
Now, it can be easily seen that the camera coordinate system can be trans-
lated to the robot coordinate system by the relationship (13.13).
⎛ X v ⎞ ⎛⎜ X c ⎞⎟
iv
⎜ ⎟
⎜ Yv ⎟ = ⎜ Yc ⎟
iv
⎜ Z ⎟ ⎜ Z iv ⎟⎟
⎜
⎝ v⎠ ⎝ c ⎠
⎛ 0 0 1 ⎞⎛ cos θ1 sin θ1 0⎞
⎜ ⎟⎜ ⎟
= ⎜ cos ψ 1 sin ψ 1 0 ⎟⎜ 0 0 1⎟
⎜ − sin ψ cos ψ 0 ⎟⎜ − sin θ cos θ 0 ⎟⎠
⎝ 1 1 ⎠⎝ 1 1
⎛ cos φ1 sin φ1 0 ⎞⎛ X c − x c ⎞
⎜ ⎟⎜ ⎟
⎜ − sin φ1 cos φ1 0 ⎟⎜ Yc − y c ⎟ (13.13)
⎜ 0 0 1 ⎟⎠⎜⎝ Z c − z c ⎟⎠
⎝
13.6 Transformation to Global Coordinate System 217
⎛ X 'v ⎞ ⎛ X v − x v ⎞
⎜ ⎟ ⎜ ⎟
⎜ Yv' ⎟ = ⎜ Yv − y v ⎟ (13.14)
⎜⎜ ' ⎟⎟ ⎜ ⎟
⎝ Zv ⎠ ⎝ Zv − z v ⎠
Step 2: Rotation about the Zv′ axis by φ2: This rotation is accomplished
by rotation of the Xv′–Yv′ plane about the Zv′ axis by φ2, where φ2 is the an-
gle between the Yv′ and Y0 axes. It is assumed here that the Z axis of both
coordinate systems coincides (assume the floor to be the X0–Y0 plane).
Thus the following relationship is obtained
i.e.
⎛ X 0 ⎞ ⎛ cos φ 2 sin φ 2 0 ⎞⎛ X v − x v ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ Y0 ⎟ = ⎜ − sin φ 2 cos φ 2 0 ⎟⎜ Yv − y v ⎟ (13 .15 )
⎜Z ⎟ ⎜ 0 0 1 ⎟⎠⎜⎝ Z v − z v ⎟⎠
⎝ 0⎠ ⎝
The relationship between the camera and the robot coordinate system was
obtained in (13.13) and the relationship between the robot and the global
218 13 Imaging Geometry
⎛1 0 0 0⎞
⎛ ku ⎞ ⎛ 1 0 0 0 ⎞⎜ ⎟
⎜ ⎟ ⎜ ⎟⎜ 0 1 0 0⎟
⎜ kv ⎟ = ⎜ 0 1 0 0 ⎟⎜
⎜ k ⎟ ⎜ 0 0 −1 f 0 0 −1 f⎟
⎝ ⎠ ⎝ 1 ⎟⎠⎜⎜ ⎟
⎝0 0 0 1 ⎟⎠
⎛1 0 0 0 ⎞⎛ cos φ sin φ 0 ⎞
⎜ ⎟⎜ ⎟
⎜ 0 cos θ − sin θ 0 ⎟⎜ 0 1 0 0⎟
⎜ 0 sin A cos A 1 ⎟⎜ − sin φ 0 cos φ 0 ⎟
⎜ ⎟⎜ ⎟
⎜0 0 0 1 ⎟⎠⎜⎝ 0 0 0 1 ⎟⎠
⎝
⎛ cos ψ − sin ψ 0 0 ⎞⎛ 1 0 0 − x 0 ⎞⎛ X ⎞
⎜ ⎟⎜ ⎟⎜ ⎟
⎜ sin ψ cos ψ 0 0 ⎟⎜ 0 1 0 − y 0 ⎟⎜ Y ⎟
⎜ 0 (13.16)
0 1 0 ⎟⎜ 0 0 1 − z 0 ⎟⎜ Z ⎟
⎜ ⎟⎜ ⎟⎜ ⎟
⎜ 0 0 0 1 ⎟⎠⎜⎝ 0 0 0 1 ⎟⎠⎜⎝ 1 ⎟⎠
⎝
⎛ t 11 t 12 t 13 t 14 ⎞
⎜ ⎟
T = ⎜ t 21 t 22 t 23 t 24 ⎟
⎜t t 32 t 33 t 34 ⎟⎠
⎝ 31
⎛1 0 0 0 ⎞⎛ 1 0 0 0⎞
⎛1 0 0 0 ⎞⎜ ⎟⎜ ⎟
⎜ ⎟⎜ 0 1 0 0 ⎟⎜ 0 cos A − sin A 0⎟
= ⎜0 1 0 0 ⎟⎜
⎜0 0 −1 f 0 0 −1 f ⎟⎜ 0 sin A cos A 1⎟
⎝ 1 ⎟⎠⎜⎜ ⎟⎜ ⎟
⎝0 0 0 1 ⎟⎠⎜⎝ 0 0 0 1 ⎟⎠
⎛ cos B 0 sin B 0 ⎞⎛ cos C − sin C 0 0 ⎞⎛ 1 0 0 − x0 ⎞
⎜ ⎟⎜ ⎟⎜ ⎟
⎜ 0 1 0 0 ⎟⎜ sin C cos C 0 0 ⎟⎜ 0 1 0 − y0 ⎟
⎜ − sin B (13.17)
0 cos B 0 ⎟⎜ 0 0 1 0 ⎟⎜ 0 0 1 − z0 ⎟
⎜ ⎟⎜ ⎟⎜ ⎟
⎜ 0 0 0 1 ⎟⎠⎜⎝ 0 0 0 1 ⎟⎠⎜⎝ 0 0 0 1 ⎟⎠
⎝
Xc
Fig. 13.12 (b) Pan angle of the camera with the reference coordinate system; (c)
Tilt angle of the camera with the reference coordinate system
13.7 Summary
This chapter briefly highlights robot perception and the process of image
formation using perspective projection geometry. The expression for de-
termining the perspective matrix of the camera, which transforms 3D ob-
ject points onto the image plane, has been derived.
14 Image Capture Program
14.1 Introduction
In the last chapter we saw that vision is one of the important human senses
and this is also the case for robots. In this chapter we will discuss how to
capture the gray and color images using a camera from the surroundings.
Here the image is captured by the camera fitted to the robot and controlled
from a remote client. The program is developed in a client–server para-
digm. During the run session, the color images are continuously being sent
to the client. When the user at the client requests a color image, the color
image displayed on the client screen is selected, and when the grayscale
image is required the color image is converted to grayscale in the client.
As the color images have larger bandwidth, transmitting them directly
would require a substantial amount of time and memory as well. There-
fore, run-time encoding is used in the server program, which is discussed
below.
The run-length encoding and server and client algorithm is given below.
The server program and the client program are given in Listings 14.1 and
14.2 respectively at the website of the book. The program log session is
given below and the output is illustrated in Figs. 14.1 and 14.2.
flag = true
If gray scale
flag =false
If cross
Goto Step 6.
Step 6: Stop.
14.3 Summary
It can be seen in Fig. 14.1 that there are two buttons “Color” and “Gray-
Scale”. When the “Color” button is pressed, the color image from the robot
server is displayed in the Java frame, while when the “GrayScale” button
is pressed the color image is converted into grayscale and displayed. Gen-
erally the image manipulations are carried out on grayscale images.
15 Building 3D Perception Using a Kalman Filter
15.1 Introduction
Fig. 15.3. A 3D affine plane EFGH that passes through (0,0,−p) and normal to the
plane passing through (0, 0, 0) and (a, b, 1) can be represented by three parameters
a, b, p
∂f i
Mi = (15.1)
∂a
∂f i
y i = −f i ( x *i , a i −1 ) + [ ] * (a − a *i −1 )
∂a ( x i ,a i −1 )
∂f i ∂f
Wi = E[ w i w iT ] = [ ] * ∧ i [[ i ] * ]T (15.2)
∂x i i −1
( x , a ) ∂x i i −1
( x , a )
Ki = Si – 1 Mi T (Wi + Mi Si – 1Mi T) -1
(15.3)
ai* = ai – 1* + Ki ( yi – Mi ai –1*) (15.4)
Si = (I – Ki Mi ) Si – 1 (15.5)
The algorithm is initialized with a large S0. The values of yi, Mi, Wi are
computed following their above definitions. a0 is initialized as a null vec-
tor. The algorithm then continues iterating in sequence until Si comes be-
low a predefined threshold. The resulting ai after termination of the algo-
rithm is the desired estimator. A schematic diagram depicting the use of
EKF in estimating noise-free geometric parameters from noisy 2D images
is presented in Fig. 15.4.
15.4 Experiments and Estimation 231
S = E[(a
0 0
− a0* )(a0 − a0* )T ]
S i = ( I − K i M i ) S i −1
Fig. 15.5. The trajectory of camera movement by a robot R around the block A to
grab its image from 24 different locations, denoted by triangles. Grabbed images
at a few locations are shown
15.4 Experiments and Estimation 233
Set I
Set II
Set III
Set IV
⎡t ⋅ u − t ⎤
yi = ⎢ 34 i 34 ⎥ (15.6)
⎣ t 34 ⋅ vi − t 34 ⎦
⎡ − ( u i t 3 − t1 ) T ⎤
Mi = ⎢ T⎥
(15.7)
⎣− ( vi t 3 − t 2 ) ⎦
∂f ⎛ − t 3 ⋅ a i −1 − t 34 0 ⎞
wi = =⎜ ⎟ (15.8)
∂x i ⎜⎝ 0 − t 3 ⋅ a i −1 − t 34 ⎟⎠
Further, a = estimation vector = [x, y, z]T with initial value of [0, 0, 0]T;
and with a very large initial covariance matrix So, which is of size 3×3 in
this case.
The first two iterations of the estimation process of reconstructing the
3D point from the multiple 2D image points is given in Listings 15.1 and
15.2 respectively. The inputs of Box 1 are a 2D point (u1,v1)= (−2.7, 1.3)
and a set of camera parameters x0=36.5, y0=98.5, z0=28.5, A=2.793,
B=−1.97, C=0. The output of Box 1 is the 3D point (x, y, z)= (22.11, 6.84,
−19.57) and the covariance matrix is
238 15 Building 3D Perception Using a Kalman Filter
Similarly the input of Box 2 is the 2D point (u2,v2)= (−2.25, 1.3) and a new
set of camera parameters x0=27.5, y0=97.5, z0=28.5, A=3.14, B=−1.97,
C=0. The output of Box 2 is the 3D point (x, y, z)= (32.04, 63.64, 10.44)
and the covariance matrix is
Fig. 15.6. Extraction of the 3D points from six 2D image points. 2D points A1
through A6 have been fused to point A by Kalman filtering. The other points B, C,
D, E, F, F in the figure have been reconstructed similarly
15.4 Experiments and Estimation 239
Listing 15.1
First iteration in the estimation process of 3D point reconstruction from noisy 2D
points using a Kalman filter.
Substituting the first value of the measurement vector (xi) that is taken from image
= (u1, v1) = (−2.7, 1.3)
The camera parameters: (x0, y0, z0, A, B, C) = (36.5, 98.5, 28.5, 2.793, −1.97, 0)
The perspective matrix for the above camera parameter can be calculated by using
following expression.
t11 t12 t13 t14 −0.135 0.049 0 0.09
T= t21 t22 t23 t24 = 0.019 0.053 −0.13 −2.16
t31 t32 t33 t34 −0.002 −0.008 1.0 1.0
−6.67 1.01
K1 = Kalman Gain = S0*M1T*(W1+ M1*S0*M1T) = 1.33 3.05
−0.54 6.01
22.11
State estimator a1 = a0+ K1*(y1−M1*a0) = 6.84
−19.57
Listing 15.2
Second iteration in the estimation process of 3D point reconstruction from noisy
2D points using a Kalman filter.
Initial State vector a1 = [a11, a21, a31] = [22.11 6.84 −19.57 ]T (from 1st iteration).
Initial error covariance matrix S1 (from 1st iteration)=
232.6 1192.9 627.5
1192.9 7699.3 4021.5
627.5 4021.5 161.7
−0.154 0 0 4.226
0 0.060 −0.141 −1.849
0 −0.009 1.0 1.0
−3.192 −0.039
K2 = Kalman Gain = S1*M2T*(W2+ M2*S1*M2T) = −18.276 1.756
−9.640 −2.932
32.04
State estimator a2 = a1+ K2*(y2−M2*a1) = 63.64
10.44
and this will continue until all the measurement vector is exhausted or up to the
specified covariance error.
15.4 Experiments and Estimation 241
The response of the Kalman filter with subsequent 2D image point in-
puts for reconstruction of the 3D points is presented in figure 15.6. The 3D
reconstruction of vertex A of the wooden block W is estimated recursively
by providing the 2D points as given below.
1200
1000
Covariance Error
800
600
400
200
0
1 2 3 4 5 6
Iterations
⎡x ⎤
yi = ⎢ i ⎥ (15.9)
⎣yi ⎦
⎡z 0 1 0⎤
Mi = ⎢ i (15.10)
⎣ 0 zi 0 1⎥⎦
∂f ⎛ − 1 0 a i −1 ⎞
=⎜ ⎟ (15.11)
∂x i ⎜⎝ 0 − 1 b i −1 ⎟⎠
Further, a0 is the initial estimation vector = [a0, b0, p0, q0]T which may be
assumed any arbitrary value such as [0 0 0 0] or may be computed from
first two points as follows:
x 2 − x1 y 2 − y1
a 0 = ; b0 =
z 2 − z1 z 2 − z1
z 2 x1 − z1x 2 z 2 y1 − z1 y 2
p0 = ; q 0 = (15.12)
z 2 − z1 z 2 − z1
Listing 15.3
First iteration in the process of 3D line estimation from 3D points using a Kal-
man filter.
9999 0 0 0
0 9999 0 0
0 0 999 0
0 0 0 999
Submitting the first measurement vector (x1, y1, z1) = (8.5 2.0 2.5)
y1 = x1 = 8.5
y1 2.0
M1 = z1 0 1 0 = 2.5 0 1 0
0 z1 0 1 0 2 0 1
W 1= −1 0 a0 −1 0 = −1.0 0
0 −1 b0 0 −1 0 1.0
a0 b0
0.394 0
K1 = Kalman Gain = S0*M1T*(W1+ M1*S0*M1T) = 0 0.394
0.157 0
0 0.016
157.17 0 −393.32 0
0 157.48 0 −393.30
−393.32 0 983.28 0
0 −393.30 0 983.28
15.4 Experiments and Estimation 245
Listing 15.4
Second Iteration in the process of 3D line estimation from 3D points using a Kal-
man filter.
Initial State vector a = [a0, b0, p0 q0] = [3.34 0.78 0.13 0.031]T (from 1st iteration).
Initial error covariance matrix S1 (from 1st iteration) =
157.17 0 −393.32 0
0 157.48 0 −393.30
−393.32 0 983.28 0
0 −393.30 0 983.28
Now substituting the second measurement vector (x2, y2, z2) = (9.0, 2.5, 2.7)
y2 = x2 = 9.0
y2 2.5
M2 = z2 0 1 0 = 2.7 0 1 0
0 z2 0 1 0 2.7 0 1
2.12 −0.64
K2 = Kalman Gain = S1*M2T*(W2+ M2*S1*M2T) = −0.666 3.76
−5.38 1.64
1.64 −9.28
and this will continue until all the measurement vector is exhausted or up to the
specified covariance error.
246 15 Building 3D Perception Using a Kalman Filter
For the reconstruction of the 3D plane, the Kalman filter can also be em-
ployed with a different set of measurement and estimation vectors. For the
case when the plane is not parallel to Z axis, the vectors can be represented
as follows:
After linearization, the following expressions can be derived for the esti-
mation.
y i = −z i (15.14)
M i = [x i y i 1] (15.15)
∂f
= [a i −1 b i −1 1] (15.16)
∂x
Listing 15.5
First iteration in the process of 3D plane reconstruction from 3D points using a
Kalman filter.
9999 0 0
0 9999 0
0 0 999
y1 = [−z1] = [−3.0]
M1 = [x1 y1 1] = [ 0 0 1]
W1= a0 b0 1 a0 = [1]
b0
1
0
K1 = Kalman Gain = S0*M1T*(W1+ M1*S0*M1T) = 0
0.999
9999 0 0
0 9999 0
0 0 0.998
248 15 Building 3D Perception Using a Kalman Filter
Listing 15.6
Second iteration in the process of 3D plane reconstruction from 3D points using a
Kalman filter.
9999 0 0
0 9999 0
0 0 0.998
submitting the second measurement vector [x2, y2, z2] = [3.2 2.2 3.1]
Y2 = [−z2] = [−3.1]
W 1= a1 b1 1 a1 = [1]
b1
1
0.212
K2 = Kalman Gain = S1*M2T*(W2+ M2*S1*M2T) = 0.145
0
and this will continue until all the measurement vector is exhausted or up to the
specified covariance error.
15.5 Correspondence Problem in 3D Recovery 249
Now computing the Euclidean distance between F and A' through H', it is
clear that the distance between F and F' is the least. Thus point F' in image
W2 corresponds to F in image W1.
15.6 Summary
This chapter first presented the minimal representation for the 2D line, 3D
line and 3D plane and then discussed the technique for estimation of the
3D parameter of the planar objects using an extended Kalman filter. The
results obtained from computer simulations demonstrate that the 3D sur-
face for planar objects can be reconstructed from multiple 2D images of
the same object. In the next chapter the client–server program for robot
perception will be covered.
16 Program for 3D Perception
16.1 Introduction
The client and server flow charts used for the 3D perception program are
illustrated in Figs. 16.1 and 16.2 and their sample programs written in C++
and Java are given in Listings 16.1 and 16.2 respectively at the website of
252 16 Program for 3D Perception
the book. The program output with log session is depicted in Figs. 16.3
through 16.9.
Start
Yes
count <N
No
Stop
Start
Display
image
Yes
count <N
No
Obtain 2D coor-
dinates for each
image
Stop
1000|6|
1000 6
one
phi=80.00 and dist=347.30
TCP connection status = 4.
Could not connect to simulator, connecting to robot
through serial.
IEEE 1394 interface open request
1 card(s) found, 2 node(s)
Checking card 0, node 0
Vitana api addr: 78080600
Vendor length is 10
Vendor is: VITANA
Model length is 10
Model is: PixeLINK(tm)
Camera found at node 0 0: VITANA PixeLINK(tm)
Camera ISO bandwidth needed: A10
Max_Image_Size_Inq: 05080408
Unit_Size_Inq: 00080008 (0)
Image_Size_Inq: 05000400 (0)
Frame_Rate_min: 0000000E (0)
Frame_Rate_max: 000000A0 (0)
Frame_Rate_def: 00000011 (0)
Flags: 00000000 (0)
PCS2112 ver 0x30
Imager reset starting...
Imager reset succeeded
Imager ready.
Camera ISO speed set to 400 Mb/sec
Camera ISO parameters: 2000000
Opened frame grabber.
Size: 320/1280 240/960
Size: 320/1280 240/960
Starting DMA
Camera ISO bandwidth needed: A10 (2576)
w, h: 640, 480
frame bytes: 614400
Size: 196608
buf size: 196608
Iso Thread running..., dmafd = 10 (43285000 42ADA010)
16.2 Flow Chart and Source Code for 3D Perception 255
RECD
Stopping DMA
ISO thread terminated
turn -80.00
move 347.30
turn 100.00
Size: 320/1280 240/960
Starting DMA
Camera ISO bandwidth needed: A10 (2576)
w, h: 640, 480
frame bytes: 614400
Size: 196608
buf size: 196608
Iso Thread running..., dmafd = 10 (43285000 42ADA010)
DBS: 161 FN: 1 QPC: 1 MAX_DBS: 4
54
SEND
RECD
Stopping DMA
ISO thread terminated
turn -80.00
move 347.30
turn 100.00
Size: 320/1280 240/960
Starting DMA
Camera ISO bandwidth needed: A10 (2576)
w, h: 640, 480
frame bytes: 614400
Size: 196608
buf size: 196608
Iso Thread running..., dmafd = 10 (43285000 42ADA010)
DBS: 161 FN: 1 QPC: 1 MAX_DBS: 4
256 16 Program for 3D Perception
54
SEND
RECD
Stopping DMA
ISO thread terminated
turn -80.00
move 347.30
turn 100.00
Size: 320/1280 240/960
Starting DMA
Camera ISO bandwidth needed: A10 (2576)
w, h: 640, 480
frame bytes: 614400
Size: 196608
buf size: 196608
Iso Thread running..., dmafd = 10 (43285000 42ADA010)
DBS: 161 FN: 1 QPC: 1 MAX_DBS: 4
54
SEND
RECD
Stopping DMA
ISO thread terminated
turn -80.00
move 347.30
turn 100.00
Size: 320/1280 240/960
Starting DMA
Camera ISO bandwidth needed: A10 (2576)
w, h: 640, 480
frame bytes: 614400
Size: 196608
buf size: 196608
Iso Thread running..., dmafd = 10 (43285000 42ADA010)
DBS: 161 FN: 1 QPC: 1 MAX_DBS: 4
54
SEND
RECD
Stopping DMA
ISO thread terminated
turn -80.00
move 347.30
turn 100.00
Size: 320/1280 240/960
Starting DMA
16.2 Flow Chart and Source Code for 3D Perception 257
RECD
Stopping DMA
ISO thread terminated
turn -80.00
move 347.30
turn 100.00
Done , exiting
Disconnecting from robot.
Lost connection
Closing video device
Fig. 16.4. Output window depicts the selection of the first point
Fig. 16.5. Output window depicts the selection of the second point
16.2 Flow Chart and Source Code for 3D Perception 259
Fig. 16.6. Output window depicts the selection of the third point
Fig. 16.7. Output window depicts the selection of the fourth point
260 16 Program for 3D Perception
Fig. 16.8. Output window depicts the selection of the fifth point
Fig. 16.9. Output window depicts the selection of the sixth point
After starting of the server program, it opens a socket and listens for a cli-
ent request. When the client is connected to the server, it launches the in-
put window where the user enters the required input, such as the radius for
the robot path and the number of images to be taken. The file name by
which the images will be stored in the robot must also be specified in this
window, which can be seen in Fig. 16.3. When the “Submit” button is
pressed the server starts the Sampler procedure and the images are sent one
16.2 Flow Chart and Source Code for 3D Perception 261
by one, which are depicted in Figs. 16.4 through 16.9. The output window
has a drop-down list using which one may select the image number. After
the images are available at the client the user can specify the fixed point of
interest in each image by clicking on the image at the desired point. These
2D values along with the robot position and camera parameter received
from the server will be stored in a file named [Link] when the “Save”
button is pressed, which is given in Table 16.1. The values stored in in-
[Link] are data for the images shown in Figs. 16.4 through 16.9.
16.3 Summary
This chapter has described the program for taking 2D images from various
viewpoints in the surroundings of the robot and storing them in a given file
and later using this information for reconstruction of 3D points using the
Kalman filter. The source code of the program is available in Listing 16.3
at the website of the book. The input to the program is given from in-
[Link] shown in Table 16.1 and the program generates the output
shown in Table 16.2.
17 Perceptions of Non-planar Surfaces
17.1 Introduction
∂g ( x , y) ∂g ( x , y)
g1 = and g2 =
∂x ∂y
The resulting gradient can be evaluated by the vector addition of g1 and g2
and is given by
[
g = g12 + g 22 ]
1/ 2 ⎛g
and phase φ = tan −1 ⎜⎜ 1
⎞
⎟⎟
⎝ g2 ⎠
A pixel is said to lie on an edge if the gradient g is above a specified
threshold. Based on this concept, various types of edge detection filters
are available in the literature [Clark, 1989; Gonzalez, 1993; Heijden, 1995;
Fram, 1975; Marr, 1980]. The gradient filter, compass filter and Laplace
filter are a few among them. The common gradient filters such as Prewitt,
Sobel and isotropic filters compute horizontal and vertical differences of
264 17 Perceptions of Non-planar Surfaces
local sums and reduce the effect of noise in the image data. All these fil-
ters have desirable properties of yielding zeros for uniform regions.
Computer vision systems often demand the segmentation of a scene into
constituent objects, which is based on the object boundaries. The object
boundary is represented by the edge, which is nothing but an abrupt
change in the gray levels. A spatial derivative of the image f(x, y) assumes
a local maximum in the direction of an edge shown in Fig. 17.1, which is
used to measure the gradient of f along r in a direction θ.
f (x, y) Edge
fy θg
fx
X
∂f ∂f ∂x ∂f ∂y
= . + . (17.1)
∂r ∂x ∂r ∂y ∂r
= f x cos θ + f y sin θ
∂f ∂ ⎛ ∂f ⎞
The maximum value of is obtained when ⎜ ⎟ = 0 , i.e.
∂r ∂θ ⎝ ∂r ⎠
17.2 Methods of Edge Detection 265
− f x sin θ + f y cos θ = 0
⎛ fy ⎞
⇒ θ g = tan −1 ⎜⎜ ⎟⎟
⎝ fx ⎠
⎛ fy ⎞
⎜ ⎟ = f x2 + f y2 (17.2)
⎜f ⎟
⎝ x ⎠ max
Based on these equations, there are two types of edge detection operators
are there, such as gradient operators and compass operators, also called as
masks. The operators represent a finite difference approximation of either
∂f
the orthogonal gradients fx , fy or the directional gradient . Let H de-
∂r
notes a p × p mask. For an arbitrary image U the inner product (H operated
on U) at location (m, n) is given by the correlation
Gradient operators: There are pairs of masks H1 and H2, which measure
the gradient of an image u (m, n) in orthogonal directions.
Let
g 1 ( m , n ) Δ U , H1 m, n and g 2 (m , n )Δ U , H 2 m ,n
where g1 and g2 are the horizontal and vertical gradient vectors, respec-
tively.
Then the magnitude and direction of the gradient vector are given by
Some common gradient operators are Prewitt’s operator and Sobel’s op-
erator having the form given below:
H1 H2
⎡− 1 0 1⎤ ⎡− 1 − 1 − 1⎤
⎢− 1 [0] 1⎥⎥ ⎢ 0 [0] 0 ⎥
Prewitt’s operator ⎢ ⎢ ⎥
⎢⎣− 1 0 1⎥⎦ ⎢⎣ 1 1 1 ⎥⎦
⎡ −1 0 1⎤ ⎡− 1 − 2 − 1⎤
⎢− 2 [0] 2⎥⎥ ⎢ 0 [0] 0 ⎥
Sobel’s operator ⎢ ⎢ ⎥
⎢⎣ − 1 0 1⎥⎦ ⎢⎣ 1 2 1 ⎥⎦
Edge maps generated by the above operators usually have thick solid
lines as boundaries which themselves may have two edges. Thinning algo-
rithms help to transform such an image to a set of simple digital arcs,
which lie roughly along the medial axes.
ing dynamic programming to find the optimum path between two given
pixels on the edge. The procedure for tracking the curve from the grabbed
image is given in Listing 17.1.
Listing 17.1 Procedure for tracking of the curve from the grabbed image
____________________________________________________________
Begin:
Find image // Collect the image (Im) from the camera of
the robot and transfer it to the client machine //
Find the pixel matrix (Pm) from the image.
If:
The image is a color image
Then:
If: G > T
Then:
It is an edge.
Else:
End for
Arrange the points obtained by the above procedure to
represent a continuous curve.
End for
End;
_______________________________________________________
Curve fitting: For a given set of points, finding the equation of a curve of
best fit for the given values is called curve fitting. Once the points defining
a curve are traced from the edge map, the problem becomes one of finding
an equation for the arbitrary constants, which best defines the curve. One
may proceed using one of the following methods: (i) graphical method; (ii)
method of least squares; (iii) method of moments and (iv) method of group
averages.
When the curve representing the given data is a linear law, y = mx + c,
the graphical method proceeds as follows:
268 17 Perceptions of Non-planar Surfaces
When the points are not approximated by a straight line, one may generate
a smooth curve, using the law governing the curve and reduce it to linear
form. The graphical method, however, fails to produce an accurate and
unique fit in this case. The principle of least squares does not help much to
determine the form of the approximate curve which can fit given data. It
determines the best possible coefficient in the equation when the nature of
the curve is known a priori. As the order of the polynomial in (17.1) in-
creases it becomes exceedingly difficult to solve the equations. Moreover
the principle is hard to implement on curves defined by quadratic (or
higher) equations in both x and y (e.g. the family of curves given by
x2 y2
+ = 1 , i.e. the circle, ellipse and hyperbola).
a2 b2
This chapter aims at finding an alternative method to predict the nature
of the curve. This method is a graphical method to estimate the curvature
of a set of points. The points extracted from the edges of the image should
have in good proximity and sufficient continuity. Every curve has a char-
acteristic slope changing pattern, which can be found using the tangents, at
successive points in the curve. Since it is difficult to predict tangency at all
instantaneous point we shall study the secants which cut chords of equal
length such that the chords form a continuous set of connected line seg-
ments. Therefore we will study the pattern of a piecewise linear approxi-
mation of curve. This principle is demonstrated for the case of a circle and
an ellipse in Fig. 17.2.
The curve is approximated to form a continuously connected line seg-
ment. The size of the line segment is approximated to the curve with a
threshold value of slope. The piecewise linear approximation assumes that
the slope of each line segment approximates the tangent to the curve at the
medial point and that the curve does not change abruptly in between two
such points, and such changes would be removed as noise. The change in
slope from one line segment to other is represented by the angles θ1, θ2,…
and these can be observed as a pattern characteristic of the curve. The line
segments have been extended beyond the curve to form secants for ease of
visual inspection.
17.3 Curve Tracking and Curve Fitting 269
Fig. 17.2. The slope variations in a piecewise linear approximation of circular and
elliptic curves
piecewise linear approximation theory. This theory based on the fact that
every curve exhibits a distinct slope pattern which can be studied from
the differential angle formed by secants of equal length cut successively
through the curve.
The flow charts for the server and client program are illustrated in Figs.
17.3 and 17.4 respectively and the source code for the server and the client
are given in Listing 17.3 and Listing 17.4 respectively at the website of the
book. The program log session is given below followed by program output
shown in Figs. 17.5 and 17.6.
Start
Is inter- Yes
Stop
rupted
No
Yes
count
<320x240
No
Start
Yes No
Is inter- Whether
rupted Completed
Yes
Convert to
Yes Gray Scale
count<
320 x 240
No H= horizontal gradient
V= vertical gradient
2 2
Read RGB pixel value G = sqrt (H + V )
from server, Increment
count
Display Result
During the program execution, the client front end displays the output as
shown in the first window of Fig. 17.5. This image is grabbed by the ro-
bot’s camera and the second window displays the edge map, as generated
by the program. The window provides two control buttons namely
“HOLD” and “PREDICT”. The “HOLD” button serves to freeze the video
frame so that a steady picture may be used for further processing. A por-
tion of the image is then selected on the edge-map using the mouse. The
“PREDICT” button launches the curve recognition program for the se-
lected portion and the result is displayed as shown in Fig. 17.6. The gray
lines represent a possible circular region with the break lines showing de-
viation. The effect of noisy image however is a limitation to the perform-
ance of the program.
17.5 Summary
The task of curve fitting becomes exceedingly difficult and error prone in
real-time visual feedback robotic systems. Thus predictions based on tradi-
tional curve fitting methods do not provide satisfactory accuracy in a noisy
visual environment. It is therefore required to approximate a certain length
of the obtained curve points to a known law so that the effects of noise can
be minimized. Such curve-fitting algorithms, however, lead to tedious cal-
culations when the nature of the curve is of second or higher order. In this
experiment, an alternative to traditional curve-fitting algorithms is pro-
posed by assuming the nature of the curve as being piecewise linear. The
experiment has produced satisfactory results. The effect of a noisy image,
however, is a limitation on the performance of the program.
18 Intelligent Garbage Collection
18.1 Introduction
The client–server algorithms are given in Listings 18.1 and 18.2 and their
programs written in C++ and Java are given in Listings 18.3 and 18.4 re-
spectively at the website of the book. The garbage collection program out-
put with program log session is depicted in Fig. 18.1.
278 18 Intelligent Garbage Collection
18.3 Summary
In the main menu, there are four buttons, namely “Get Image”, “Color”,
“Go” and “Stop”. The function of the first button Get Image is to get the
image from the server usually to take the image of the colored box. This is
used to set the color of the box during the run time of the program. After
the image of the box is received, which will be shown in the left window,
282 18 Intelligent Garbage Collection
the Color button is pressed. After that, all other buttons will be deactivated
and, therefore, the portion of the image that contains the color of the box is
selected. Then, the color of the box taken by the program is shown in the
Box Color region. If the color of the box is not taken correctly or we want
to select the color of the box again, the Get Image button is clicked again,
and we proceed as before.
Once the user is satisfied with the color of the box, then the Go button is
clicked. This makes the robot search for the box in its environment. If it
finds one, then it moves towards it until it grabs it and it drops it at the ori-
gin. After dropping at the origin it moves back to its original position from
where the box was collected. Again, it continues to scan the environment.
This program runs continuously until the window is closed. If for some
reasons or other the user wants to stop the robot, the Stop button is clicked,
which stops the robot in its next cycle of getting the image.
The program has two sliders, i.e. Threshold value and Max. count value,
for checking whether the image contains the color box or not. The program
finds out which pixels are in close range of color as compared to the color
of the box. This range is set by the Threshold value slider. Once the color
box is found in the image, the user has to decide in which direction the ro-
bot should move in order to catch the object. For which the right window
is divided into 12 parts (3 × 4) and we count the number of pixels close to
the color of the Color box in each sub-window. The sub-window having
the largest count decides the direction of the robot. This count is set by the
Max. count value slider.
References
[Aloimonos,1987] Aloimonos, J., Weiss, I., and Bandopadhay, A., “Active vi-
sion”, International Journal of Computer Vision, vol. 1, no. 4, pp. 333–356,
1987.
[Arbib, 1981] Arbib, M., “Perceptual structures and distributed motor control”, in
Handbook of Physiology—The Nervous System II, ed. V.B. Brooks, Bethesda,
Maryland: American Physiological Society, pp. 1449–1465, 1981.
[Asada, 1990] Asada, M., “Map Building for a mobile robot from sensory data”,
IEEE Transaction on Systems, Man and Cybernetics, vol. 37, no. 6, pp. 1326–
1336, Nov./Dec., 1990.
[Ayache, 1987] Ayache, N., Faugeras, O.D., “Building a consistent 3D representa-
tion of the mobile robot environment by combining multi stereo views”, Pro-
ceedings of the International Joint Conference on Artificial Intelligence, Au-
gust 1987.
[Ayache, 1991] Ayache, N., Artificial Vision for Mobile Robot, The MIT Press,
Massachusetts, 1991.
[Baldi, 1995] Baldi, P.F., Hornik, K., “Learning in linear neural networks: a sur-
vey”, IEEE Transactions on Neural Networks, vol. 6. no. 4, pp. 837–857, July
1995.
[Ballard, 1991] Ballard, D.H., “Animate vision”, Journal of Artificial Intelligence,
vol. 48, no. 1, pp. 57–86, 1991.
[Bezdek, 1991] Bezdek, J.C., Ed., Pattern Recognition with Fuzzy Objective
Function Algorithms, Kluwer Academic Press, 1991.
[Bharick, 1984] Bharick, H.P., “Semantic memory content in permastore: fifty
years of memory for Spanish learned in school”, Journal of Experimental Psy-
chology: General, Vol. 120, pp. 20–33, 1984.
[Borenstain, 1996] Borenstain, J., Everett, H.R. and Fang, L. Navigating Mobile
Robots: Systems and Techniques, A. K. Peter Wellesley, 1996.
[Briscoe, 1997] Briscoe, G., Caelli, T., “ABC: biologically motivated image un-
derstanding”, in Machine Learning and Image Interpretation, editor, Caelli,
T., and Bischof, W.F., Plenum Press, New York, 1997.
[Brooks, 1989] Brooks, R.A., “A robot that walks; emergent behaviors from a
carefully evolved network”, Neural Computation 1(2):253, 1989.
[Brown, 1997] Robert, G., Hwang, Patrick Y.C., Introduction to Random Signals
and Applied Kalman Filtering, John Wiley, 1997.
284 References
[Buchanan, 1993] Buchanan, B.G. and Wilkins, D.C., Eds., Readings in Knowl-
edge Acquisition and Learning: Automating the Construction and Improve-
ment of Expert Systems, Morgan Kaufmann, San Mateo, CA, 1993.
[Caelli and Bischob, 1997] Caelli, T., and Bischob, W.F., Machine Learning and
Image Interpretation, Plenum Press, New York, 1997.
[Carpenter, 1987] Carpenter, G.A., Grossberg, S., “A massively parallel architec-
ture for a self-organizing neural pattern recognition machine”, Computer Vi-
sion Graphics and Image Processing 37, pp. 54–115, 1987.
[Chang, 1986] Chang, T.M., “Semantic Memory: Facts and Models”, Psychologi-
cal Bulletin, vol. 99, pp. 199–220, 1986.
[Clark, 1989] Clark, J.J, “Authenticating edges produced by zero-crossing algo-
rithms”, IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 12, no. 8, pp. 830–831, 1989.
[Connell, 1990] Connell, J., Minimalist Mobile Robotics: A Colony-Style Architec-
ture for an Artificial Creature, Boston, Mass: Academic Press, 1990.
[Davis, 1986] Davis, L.S., and Kambhampati, S., “Multi-resolution path planning
for mobile robots”, IEEE Transactions on Robotics and automation, vol. RA-
2, no. 3, 1986.
[Dean, 1995] Dean, T., Allen, J., and Aloimonos, Y., Artificial Intelligence: The-
ory and Practice, Addison-Wesley, 1995.
[Elfes, 1987] Elfes, A., “Sonar-based real-world mapping and navigation”, IEEE
Journal of Robotics and Automation, vol. RA-3, no. 3, pp. 249–264, June,
1987.
[Feldman, 1992] Feldman, J.A., “Natural Computation and Artificial Intelli-
gence”, Plenary Lecture presented at the International Joint Conference on
Neural Networks, Baltimore, 1992.
[Fermuller and Aloimonos, 1993] Fermuller, C., and Aloimonos, Y., “Vision and
action”, Image Vision Computation, vol. 13, no.10, pp. 725–744, Dec. 1993.
[Filho, 1994] Filho, R., “Genetic algorithms programming environments”, IEEE
Transactions on Computers, vol. 26, pp. 28–43, June 1994.
[Fram, 1975] Fram, J.R. and Deutsch, E.S., “On the quantitative evaluation of
edge detection schemes and their comparison with human performance”,
IEEE Transactions on Computers, vol. C-24, no. 6, pp. 616–628, 1975.
[Gardner, 1985] Gardner, H., The Mind’s New Science: A History of the Cognitive
Revolution, New York: Basic Book, 1985.
[Goldberg, 1989] Goldberg, D.E., Genetic Algorithm in Search Optimization and
Machine Learning, Reading, MA, Addison-Wesley, 1989.
[Harlick, 1993] Harlick, R.M., Shapiro, L.G., “Computer and Robot Vision”, Ad-
dison-Wesley, Vol. 2, 1993.
[Hashimoto, 1999] Hashimoto, K., “Observer-based visual servoing”, in Control
in Robotics and Automation, edited by Ghosh, B.K., Xi, Xing, Tarn, J.J., Aca-
demic Press, 1999.
[Haykins, 1999] Haykin, S., Neural Networks: A Comprehensive Foundation,
Prentice Hall, 1999.
[Heijden, 1995] Heijden F.V., “Edge and Line Feature Extraction Based on Co-
variance Models”, IEEE Trans. on Pattern Analysis and Machine Intelligence,
vol. 17, no. 1, pp. 69–77, Jan. 1995.
References 285
[McDermott et al., 1984] McDermott, D. and Davis, E., “Planning routes through
uncertain territory”, Journal of Artificial Intelligence, vol. 22, 1984.
[Merlo et al., 1987] Merlo, X., Lanusse, A., Zavidovique B., “Optimal control of a
robot perception system”, Proceedings of IASTED International Symposium
on Expert Systems Theory and Applications, Geneve, 1987.
[Michalewicz, 1996] Michalewicz, Z., Genetic Algorithms + Data Structures =
Evolution Programs, 3rd edition, New York, Springer-Verlag, 1996.
[Michalski, 1983] Michalski, R.S., “A theory and methodology of inductive learn-
ing”, Artificial Intelligence, vol. 20, no. 2, pp. 111–161, 1983.
[Minsky, 1975] Minsky, M., “A framework for representing knowledge”, The
Psychology of Computer Vision, edited by Patrick H. Winston, McGraw-Hill,
New York, 1975.
[Mitchell, 1997] Mitchell, T.M., Machine Learning, Tata McGraw-Hill, 1997.
[Mitchell et al., 2001] Mitchell, Mark, Oldham, Jeffrey and Samuel, Alex, Ad-
vanced Linux Programming, New Riders Publisher, 2001.
[Murphy et al., 1998] Murphy, R., Kortenkamp, D., “Vision for mobile robots”,
Artificial Intelligence and Mobile Robots, AAAI Press/The MIT Press, 1998.
[Murphy, 1998] Murphy, R.R., Artificial Intelligence and Mobile Robots, AAAI
Press/The MIT Press, 1998.
[Narendra et al., 1990] Narendra, K. S. and Parthasarathi, K., “Identification and
control of dynamic system using neural networks”, IEEE Transactions on
Neural Networks, vol.1, pp. 4–27, 1990.
[Newell et al., 1972] Newell, A., and Simon, H.A., Human Problem Solving,
Englewood Cliffs, NJ: Prentice Hall, 1972.
[Pagac et al., 1998] Pagac, D., Nebot, E.M., and Durrant-Whyte, H., “An eviden-
tial approach to map-building for autonomous vehicles”, IEEE Transactions
on Robotics and Automation, vol. 14, no. 4, pp. 623–629, August, 1998.
[Patnaik et al., 1998a] Patnaik, S., Konar, A. and Mandal, A. K., “Map building
and navigation by a robotic manipulator”, Proceedings of International Con-
ference on Information Technology, Tata McGraw-Hill Publisher, New Delhi,
pp. 227–232, 1998.
[Patnaik et al., 1998b] Patnaik, S., Konar, A. and Mandal, A.K., “Navigational
planning with dynamic scenes with timed Petri nets”, Proceedings of Interna-
tional Conference on Computer and Devices for Communication, Allied Pub-
lisher, New Delhi, pp. 40–43, 1998.
[Patnaik et al., 1999a] Patnaik, S., Konar, A. and Mandal, A.K. “Constrained hi-
erarchical path planning of a robot by employing neural nets”, Proceedings of
the Fourth International Symposium on Artificial Life and Robotics, pp. 690–
693, Japan, Jan. 1999.
[Patnaik, 1999b] Patnaik, S., Building Cognition for Mobile Robot, Ph.D. Thesis
submitted to Jadavpur University, Calcutta, India, Sept., 1999.
[Patnaik et al., 1999c] Patnaik, S., Konar, A., and Mandal, A. K., “Bi-directional
associative memory for mobile robot navigation”, Proceedings of Interna-
tional Conference on Neural Network, Washington, July, 1999.
[Patnaik et al., 2003a] Patnaik, S., Karibasappa, K., “Cognition techniques and
their applications”, Technology and Business for the New Millennium, edited
by Prof. C.T. Leondes, Kluwer Academic Press, 2003.
References 287
[Patnaik et al., 2003b] Patnaik, S., Karibasappa, K., “Edge, shade and mixed range
detection by fuzzy gaussian filter for an autonomous robot”, Journal of Intel-
ligent Robotic Systems, vol.37, no.3, 2003.
[Pedrycz, 1995] Pedrycz, W., Fuzzy Sets Engineering, CRC Press, Boca Raton,
FL, 1995.
[Pomerleau et al., 1989] Pomerleau, D.A., ALVINN: An autonomous land vehicle
in a neural network, Pittsburgh, PA: Carnegie Mellon University, Technical
report CMU-CS-89–107, 1989.
[Popovic et al., 1994] Popovic, D., Bhatkar, V.P., Methods and Tools for Applied
Artificial Intelligence, Marcel Dekker Inc, 1994.
[Gonzalez, 1993] Gonzalez, R.C., Richard E.W., Digital Image Processing, Addi-
son Wesley, 1993.
[Rich et al., 1996] Rich, E., Knight, K., Artificial Intelligence, McGraw-Hill, New
York, 1996.
[Rimon, 1992] Rimon, E., Koditschek, Daniel E., “Exact robot navigation using
artificial potential functions”, IEEE Transactions on Robotics and Automa-
tion, vol. 8, no. 5, pp. 501–518, October 1992.
[Rubini, 1998] Rubini, A., Linux Device Drivers, O’Reilly, 1998.
[Rumelhart et al., 1986] Rumelhart, D.E., and McClelland, J.L., Parallel Distribu-
tion Processing: Exploration in the Microstructure of Cognition, vol. 1, Cam-
bridge, MA: MIT Press, 1986.
[Saffioti, 1997] Saffiotti, A., “Fuzzy logic in autonomous robotics: behavior coor-
dination”, in Proceedings of 6th IEEE International Conference on Fuzzy Sys-
tems, Barcelona, Spain, 1997, vol. 1, pp. 573–578.
[Samet, 1982] Samet, H., “Neighbor finding techniques for image representation
by Quadtree”, Journal of Computer Graphics and Image Processing, Vol. 18,
pp 37–57, 1982.
[Saphira, 1999] Saphira Operations and Programming Manual, Version 6.2, Au-
gust 1999.
[Schalkoff, 1997] Schalkoff, R.J., Artificial Neural Networks, McGraw-Hill,
1997.
[Sekuler et al., 1990] Sekuler, R. and Blake, R., Perception (Second edition),
McGraw-Hill, 1990.
[Sullivan, 1999] Sullivan, M.J., Vision active deformable modes in visual ser-
voing: Control in Robotics and Automation, edited by Ghosh, B.K., Xi, Xing,
Tarn, J.J., Academic Press, 1999.
[Swan, 2000] Swan, T., GNU C++ for Linux, QUE Corporation, 2000.
[Sympson, 1988] Sympson, P., Artificial Neural Nets: Concepts, Paradigms and
Applications, Pergamon Press, Oxford, 1988.
[Takahashi, 1989] Takahashi, O., and Schilling, R. J., “Motion planning in a plane
using generalized Voronoi diagrams”, IEEE Transactions on Robotics and
Automation, vol.5, no.2, 1989.
[Tanaka, 1995] Tanaka, K., “Stability and stabilizability of fuzzy-neural-liner con-
trol systems”, IEEE Transactions on Fuzzy Systems, vol. 3, no. 4, 1995.
[Taylor and Kriegman, 1998] Taylor, C.J., and Kriegman D.J., “Vision-Based Mo-
tion Planning and Exploration Algorithm for Mobile Robots”, IEEE Trans
on Robotics and Automation, vol. 14, no. 3, pp. 417-426, June, 1998.
288 References
[Trojanowski, 1997] Trojanowski, K., Michalewicz, Z., and Xiao, J., “Adding
memory to an evolutionary planner/navigator”, Proceedings of the Fourth
IEEE International Conference on Evolutionary Computation, Indianapolis,
IN, April, 1997.
[Tulving, 1987] Tulving, E., “Multiple memory systems and consciousness”, Hu-
man Neurobiology, vol.6, pp.67–80, 1987.
[Tzionas et al., 1997] Tzionas, Panagiotis G., et al. “Collision-free path planning
for a diamond-shaped robot using two-dimensional cellular automata”, IEEE
Trans. on Robotics and Automation, vol.13, no.2, 1997.
[Waltz, 1997] Waltz, D., “Neural nets and AI: time for a synthesis”, Plenary talk,
International Joint Conference on Neural Networks, Houston, vol.1, 1997.
[Winston, 1975] Winston, P.H., “Learning structural descriptions from examples”,
The Psychology of Computer Vision edited by P.H. Winston, McGraw-Hill,
New York, 1975.
[Xiao et al., 1997] Xiao, J., Michalewicz, Z., Zhang L., Trojanowski K., “Adap-
tive evolutionary planner/navigator for mobile robots”, IEEE Transactions on
Evolutionary Computation, vol. 1, no. 1, pp. 18–28, April 1997.
[Yager, 1983] Yager, R.R., “Some relationships between possibility, truth and cer-
tainty”, Fuzzy Sets and Systems, Elsevier, North Holland, vol. 11, pp. 151–
156, 1983.
[Zadeh, 1983] Zadeh, L.A., “The role of fuzzy logic in the management of uncer-
tainty in Expert systems”, Fuzzy Sets and Systems, Elsevier, North-Holland,
vol. 11, pp. 199–227, 1983.
[Zavidovique, 2002] Zavidovique, B.Y., “First steps of robotic perception: the
turning point of the 1990s”, Proceedings of the IEEE, vol. 90, no. 7, pp.1094–
1112, July 2002.
[Zimmerman, 1991] Zimmerman H.J., Fuzzy Set Theory and Its Applications,
Kluwer Academic, Dordrecht, The Netherlands, 1991.
Index
Image capture 79, 100, 101, 221 Tele-operation program 177, 180, 181
Image formation 203, 205 Temporal associative memory 68,
Image-server program 189–190, 270 69, 76
Imaging geometry 201, 205
Intelligent garbage collection 277 Wandering program 163
Cognitive Technologies
S. K. Pal, L. Polkowski, A. Skowron (Eds.):
Rough-Neural Computing.
Techniques for Computing with Words.
XXV, 734 pages. 2004
H. Prendinger, M. Ishizuka (Eds.):
Life-Like Characters.
Tools, Affective Functions, and Applications.
IX, 477 pages. 2004
H. Helbig:
Knowledge Representation and
the Semantics of Natural Language.
XVIII, 646 pages. 2006
P. M. Nugues:
An Introduction to Language Processing
with Perl and Prolog.
An Outline of Theories, Implementation,
and Application with Special Consideration
of English, French, and German.
XX, 513 pages. 2006
W. Wahlster (Ed.):
SmartKom: Foundations of Multimodal Dialogue Systems.
XVIII, 644 pages. 2006
B. Goertzel, C. Pennachin (Eds.):
Artificial General Intelligence.
XVI, 509 pages. 2007
O. Stock, M. Zancanaro (Eds.):
PEACH – Intelligent Interfaces for Museum Visits.
XVIII, 316 pages. 2007
V. Torra, Y. Narukawa:
Modeling Decisions: Information Fusion
and Aggregation Operators
XIV, 284 pages. 2007
P. Manoonpong:
Neural Preprocessing and Control
of Reactive Walking Machines.
Towards Versatile Artificial Perception–Action Systems.
XVI, 185 pages. 2007
S. Patnaik
Rob ot Cognition and Navigation
An Experiment with Mobile Robots
XVI, 290 pages. 2007