Motion Planning for Two Mobile Robots in an [602953]

Motion Planning for Two Mobile Robots in an
Environment with Obstacles by Using
Cellular Neural Networks
I. Gavriluf, A. Gacsadi', L. Tepelea', V. Tiponuf2
'University of Oradea, Str. Armatei Rodne 5,410087, Oradea, Romania,
Electronic Department Tel: +40-259-40873 5, Fax: MO-259-432789
E-mail: [anonimizat], [anonimizat], [anonimizat],
*Politelmica University from Timivoara, Applied Electronic Department,
B-dul Vasile Parvan, Nr. 2, 1900 TirniSoara, Romania, E-mail: [anonimizat].
Abstract – The paper presents P visual control algorithm based on
images, for two mobile robots in an environment with obstacles.
Ceiluisr Neural Networks (CNNs) processing techniques are used
. here for motion planning in real time of two mobile robots moving
to the same target. The algorithm cnn be extended for tfrree or
more robots. ,
I. INTRODUCTION
A challenge in autonomous robotics is the navigation in
unstructured environments using vision-based algorithms. These
algorithms should guide one or more robots from an initial
position to a target position, avoiding obstacles located between
these positions. If we take into account that the obstacles as well
as the target can move and that the obstacles can have any
shape, it becomes clear that this problem is not a trivial one.
There are several solutions to solve hs problem, each of
them being included in the global or/and local control method of
robot. The global method for path planning or robot navigation
is mlatod with the superior hierarchical level in the robot control
theoq. On the other hand, the local method could be related
wth the inferior hierarchical level in the robot control theory.
These two approaches are often used together, namely the
global planning is used for achieving a possible trajectory
avoiding obstacles, while local navigation is uscd for local
optimization of the path and for avoiding unexpzcted obstacles
[6,7,93.
Cellular neural networks (C") can be successfully used in a
wide spectrum of applications [1,2]. The CNN methods have
hen considered as a solution for images processing in mobile
robots guidance. The choice of CNNs for the visual processing
part lies on the possibility of their hardware implementation in
large networks on a single VIA chip. A variety of approaches
have been proposed to use CNNs for a singIe mobile robot path
planning which is moving in unstructured environments
[5,8,111.
Usually the environment with obstacles is divided into
discrete images and in this way it is possible to represent the
workspce in the form of an M*N anay, through a standard
neural network having M*N cells. The processed images are gray-scale, having the value of the pixel in the interval [-l,l],
known as the standard domain in CNN. For binary images,
these values could be only +1 for the black pixels and -1 for
white pixels
Ths paper is organized as follows: In Section I1 we briefly
review the cooperation between mobile robots. In Section III a
CNN algorithm for the guidance of two mobile robots *is
presented. Simulation results are shown in Section IV. Some
conclusions and future directions of the research are given in
Section V.
11. COOPERATION IN MOBILEROBOTS SYSTEMS
Research in autonomous robots has recently taken a new
approach, namely, the multi-robot approach, in which systems
are designed, that distribute to varying degrees, actuation and
sensing to perform tasks with or without some form of
cooperation. Examples requiring distributed actuation include:
floor washing, lawn moving, vacuuming, crop harvesting or
wail cleaning, all possible by one robot, without cooperation,
given enough time. On the other hand there are the cooperative
tasks, requiring more than one robot; examples include heavy
object transportation, fluid containment or fire control.
Distributed sensing tasks require the system to perceptually
c0ver.m area spatially and might include such tasks as mine
sweeping, mapping, searching or environmental monitoring.
Both cooperative and non-cooperative forms of these tasks
esist, and can be differentiated by imposed constraints such as
whether a fixed formation needs to be maintained [3,4].
Designing systems for these tasks requires architectural
decisions to be made. Architectures make use of either a
heterogeneous or a homogeneous set of robots. Explicit
communication between robots varies from none to a fully
connected topology, where each robot has access to full global
knowledge. System size ranges from a few robots to more than
100, with most systems reporting experimental results with
physical implementations having less than 10 robots.
Tash used in the study of multi-robot control include
foraging, which involves searching and retrieving items from a
given area; box-pushing,'which moves an object between two
0-7803-9029-6/05/$20.00 02005 IEEE 80 1

locations; and formations marching, where robots move while
maintaining a fixed pattern. These collective tasks have been
studied using both physical rbbots and simulation. The
questions under investigation abound. Should the composition
be a homogeneous or heterogeneous set of robots? Does
communication help improve task execution speed? What is the
most effective control structure for a multi-robot systein?
System composition, communication, and control structure all
play major roles in accomplishing tasks with multi-robot
systems. Also, systems composed of heterogeneous robots
require methods that can decompose a task and plan its
allocation based on the individual skills of the robots. This often
requires some form of negotiated cooperation with resdts being
explicitly communicated Whereas homogeneous systems,
consisting of robots with identical skill sets, alleviate the need
for task decomposition and allocation.
In this work we have studied the problem of guidance of two
homogeneous mobile robots moving toward the same target.
After the image preprocessing of the environment, the robots
use only local sensing and minimal communication.
The communication between robots can be considered like
an implicit communication because the transmission of the
information is done through the environment. Both robots are
able to detect when the other robot is situated in its vicinity in
order to avoid it.
111. THE CNN ALGORITHM FOR SIMULTANEOUS GUIDANCE OF
TWO MOBILE ROBOTS
In the current application, the two mobile robots are
considered to be placed in a plane workspace, in which there
ae only static obstacles (see Figure 1). A single camera
observes the whole environment and captures images of the
workspace at discrete moments.
camera + Target
/ Obstacles ~
Figure 1. The wakapace of the mobile robob.
The two robots have to move together toward the same
target by avoiding obstacles and in the same time avoiding the
collision between them. Robots motion will be done
sequentially to the target's position on the trajectories
generated by the motion planning algorithm. When one of rhe
robots is moving the other robot is stopped and becomes a
static obstacle. The visual motion planning of the two robots is done following the steps of the global algorithm given in
Figure 2.
l-xg
Binary image of the workspace
The start and the iqei position are identified
mobile robot 1
I
Palh planning and moving of the 1 I mobile mbot 2
I
db0t 2 reached the tam- r
Path plat~ni~~g and "ing of the
mobile robot 1
Figure 2. Motion planning algorithm for two mobile robots when they are
moving to thc same target.
The image processing is entirely performed .by cellular
neural network algorithms. The necessary steps of this
algorithm are done using space-invariant cellular neural
networks having templates of 3*3 dimensions.
After a spatial discretization of the images which correspond
to the CNN resolution, we suppose that each obstacle is
represented by at least one pixel. Instead each of the robots is
identified by a single pixel.
The binary input image is considered to be obtained from the
gray-scale image, representing the workspace, by elementary
CNN processing. In this image, the pixels having +1 value
represent the forbidden positions in the work place, in which
the robots .cannot pass, while the pixels having -1 value
represent the positions in which the robots can move. The start
positions of the two robots, and the target position ate also
considered to be identified by one binay image each.
A.
In this step of the algorithm, in the image plane a wave is
generated first [ 111. The origin of the source whch generates
the wave, is actually, the position of the target point. Through
its propagation the wave searches all the possible directions in
the environment, starting from the target point, as in Figure 3.
An image in which all the pixels have the value +I, except a
pixel that corresponds to the target position having -I value
will represent the state x[to) of the network. This image is, in Path planning and the moving of one mobile robot
802 .,

fact, the exactly opposite of the image containing the target neighborhood of the robot can be defined as a neighborhood
point. The current binary image of the workspace is used as a having the radius r=l (neighborhood 3*3) or larger,
mask image in this processing step. The image for distance (seeFigure4).
evaluation between positions of the workspace and the target,’
except the obstacles positions, could be achieved using the \
template explore.tem 11 1,131. The pixels corresponding to the
borders of the workspace, namely the pixels that are at the Robot 1
J v1 boundaries of the cellular neural network .are considered Robot w
always forbidden positions. As a result of these operations, the m-
value of the pixel corresponding to the target position in the
output image remains unchanged at its initial value -1 while
the pixels having the value +1 are going to be the forbidden
pixels wiH have values that proportionally increase with the
distance between them and the target position. Thus, starting
from the center of wave source the value of pixels is increasing
approximately with one measure unit of the distance, when the
wave radius is increasing by 1. If the environment is without
obstacles the wave has a circular propagation. positions through which the robot cannot pass. All the other
Robot 2
Robot 2
a)
Figure 4. The neighborhood of thr mobile robots having PI; (a) for robot I
Tqet when robot 2 is moving; (b) for robot 2 when robot 1 is moving.
– Tn order to obtain the above mentioned neighbarhood, a
wave around the mobile robot is generated using the template
dilationl.tem [I 31. Using this template, values of pixels from
the neighborhood of a mobile robot, which is represented, by
one pixel, become +I, thus an obstacle for the other robot.
C. Reaching of the target pint
The robots are altematively moving tp the target position. If
one of the robots has reached the target point, the algorithm
will continue for the second robot, until this one reaches the
target. The target’s neighborhood has the radius ~1, where the
robots have to arrive; fiilly, both robots will stop around the
target point, as it can be seen in Figure 5. Figure 3. The principle of determination ofthe distance in between the target
and the pinta from the workspace through wave propagation having the origin
of Lhe source in the target paint. The values of pixels in the image are
proportionally increased with the distance. siarting from Lhe origin. rFFi
After this, the algorithm chooses the optimal direction -* Rabdl RChz F&+Zl Rnbot 1
hough which the robot can move closer to the target position.
Starting from the current position, the next step of the robot
will be made on the same direction only if the value of the
pixel corresponding to the following position is smaler than
sekct.tem extended for the 8 directions is used for obtaining
the hge with the planning trajectory . The pl&g baj ectoq
in one step of the algorithm for one robot represents the portion
of the total trajectory, where the robot is moving in straight
line, without changes in the direction of the movement f I 1 ,131. -1
the value of the current position. The group of templates a) b) f)
Figure 5. Reaching target example: @)the oare when neitherrobot reaches
the large6 (b) when one of mbota reaches the we6 (0) the fmdh situation
when the both robots ~tre m the target neighburhood
Iv. THE ALGORITHM SIMULATIONRESULTS
B. Collision avoidance with the other robot development environment and toolkit under Windows), [ 131.
The neighboring area of the target and of the rohk was chosen
. path planning for robt aIso include collision with a radius r=l. An eniironment of 32*32 pixel dimension,
with obstacles having different sizes and shapes, as in Figure
6a, has been used for simulation. The final results of the In addition to the avoiding static obstacles in the
avoidance with the other robot. For this purpose we defined 9 robt area around he rpbt in the
can’t enter. Choosing he robot’s size by one pixel, fie simulation are presented in the Same
803

As it can be seen, the optimal trajectory.of robot 1, shown in
Figure 6f, was modified after meeting with robot 2, like in
Figure 6c,e.
w Tqd' -l
I
F
ri
Figure 6. Results achieved through siniuiation ofthe proposed CNN
algorithm: (a) image with environment &er the preprocessing step; – the start
points md the target points are also indicated; (b) the image obtained for
evaluating the distance in between the target and the pints from the
workspace; the images of the robis are overlapping on that image; (0) the total
trajectory of robot 1; (d) the total trajectory of robot 2; (e) the two final robots
trajectories; (f) the optimally trajectoty of robot 1 when only his robot is
moving to the target in wodispace.
V. CONCLUSIONS
The proposed motion planning algorithm for WO mobile
robots in an environment with obstacles can be done in real
time by using cellular neural network. This planning method,
based on image processing, represents an advantageous
alternative to other methods used for mobile robots navigation.
A possible improvement of the global C:" algorithm depends
on the possibility of continuously increasing the speed -of
image processing, which depends also on the Qpe of the CNN-
chip that is used. The image processing steps of this algorithm
are done using space-invariant cellular neural networks having
templates of 3*3 dimensions. The path planning algorithm can
easily be extended for three or more robots.
The total processing time is the sum of the times
corresponding to each step of the algorithm. The minimum
processing time of the step, in wiuch the evaluation of
distances between points from the workspace and the target
point is made, depends on the distance between the start and
the target position, because it is absolutely necessary for the
wave to reach, through propagation, the start position. In the
foHowing step, in which the robot moves on the chosen
direction, the necessary time is increasing with the length of the path that must be followed. The toGI number of curves
must also be taken into account when computing the total time,
namely the number of points in which a new optimal direction
is chosen to get closer to the target.
The precision of the positioning of the robot in the working
environment based on visual information could be increased if
the dimensions of the acquired images changed when the
robots approach the target. This purpose could be achieved by
adequately adjusting the position and the focus of the camera in
order to acquire only the region of interest from the image of
the working environment. A practical solution implies to
follow the robots with a mobile video camera [lo].
At each cycle, in our algorithm, one of the robots would
"wait" the stopping of the other robot. The total time between
the beginning of the algorithm and the final situation when
both robots are in the target's neighborhood, can be reduced by
introducing the predicted position of the robots at each cycle in
the CNN algorithm [ 121.
A possible further research duection would to take into
consideration a carrying task performed by two mobile robots,
using CNN processing approach.
REFERENCES
[I] L.O. Chua and L. Yang, '*Cellular Neural Networks: Theory and
Application", EEE Trans. On Circuits and Systems, (CAS), Vol. 35,
pp. 1257-1290,1988.
T. Roska and L.O. Chua, "The CNN universal machine: an analogical
array computer", IEEE Trans. on Circuits and Systems 11: Analog and
Digital Signal Racessing, Vol. 40, pp. 163-173, 1993.
C. R. Kube, H. Zhang. 'Task modeling in collective robotics", Kluwer
Academic Publishers, Autonomous Roboh, 1997.
T Balch, R.C. Arkin. "Behavior-Based Formation Control for Mutilmbot
Team", EEE Trans. on Robotics and Automation, Vol. 14, No. 6.
pp. 926 – 939,1998.
P. Szolgay, A. Katona, A. Kiss, L. Szekely, A. Vsress, "An optical robot
path kacking system", Toward the Visual Microprocessor – VLSl Design
and Use of Cellular Network Universale Machines (Toward the Visual
Microprocessor), John Wiley and Sons. 1997.
S.X. Yang, M. Meng, "An efficient neural network approach to dynamic
robot motion planning", Neural Networks, Vol. 13, pp. 143-I48,2000
T. Cecil, D. Marthaler, "A variational approach to search and path
planning using level set msthods': pp. Los Angeles. 2004.
D. L. Vilarino, C. Rekecdcy "Shortest path problem with pixels bel
snakes: Application to robot path planning", Prmeedings of the IEEE
hternational Wokshop on Cellular Neural Networks and heir
Applications, (CNNA 2004). pp. 135-140, Budapest, 2004.
R. Glasius, A. Komoda, S.Gielen. "Neural network dynamics for path
planning and obstacle avoidance" Depariment of Medical Physics and
Biophysics, University of Nijmegen. The Netherlands, 1994.
[lo] A. Gacsndi, P. Szolgay, "An analogic CNN algorithm for following
continuously moving objects", Pmceedings of the lEEE Intemational
Workshop on Cellular Neural Networks and their Applications.
(CNNA 2000). pp 99-lOY, Catania, 2000.
[11] A. Gacsadi, T. Maghiai, V. TiponuL "Path planning for a mobile robot in
an environment with obstacles using cellular ncural networlr".
International Workshop on CNN and their Applications, (CNNA 2002).
SrankfutVMain, pp. 188-194.2002.
[I21 I. Gavrilut, A. Gacsadi, 'Tmjectoly tracking and predicting using CNN",
Proceedings of the Intcmational Conference on Engineering of Modem
Electric Systems (EMES'?003), Oradea, pp. 56-61,?003.
[I31 *** "Cadetwin-99, CNN application development environment and
toolkit under Windows" Version 3.0. Analogical and Neural Computing
Laboratory, Computer and Automation Institute, Hungarian Academy OF
Science, Budapest, 1999. [2]
[31
[4]
[5]
[6]
[71
[SI
[9]
804