VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10
Swarm Optimization Approach
for Light Source Detection by Multi-robot System1
Hoang Anh Quy, Pham Minh Trien
VNU University of Engineering and Technology, 144 Xuan Thuy, Cau Giay, Hanoi, Vietnam
Abstract
Exploration and searching in unknown or hazardous environments using multi-robot systems (MRS) is
among the principal topics in robotics. There have been numerous works on searching and detection of odor, fire
or pollution sources. In this paper, a modified Particle Swarm Optimization Algorithm (PSO) was presented for
MRS on detecting light sources, namely APSO. In the proposed algorithm, an integration of conventional PSO
and Artificial Potential Field (APF) is employed to use swarm intelligence for space exploration and light source
detection. The formulas for APSO velocities are based on those of PSO and APF. Furthermore, each particle is
surrounded by an APF that forms repulsive force to prevent collision while the swarm is in operation. The
simulation results of APSO in Matlab by various scenarios confirmed the reliability and efficiency of the
proposed algorithm.
Received 04 December 2015, Revised 09 January 2016, Accepted 26 September 2016
Keywords: PSO, MRS, APF, APSO, light source detection.
1. Introduction*
because
of
its
efficiency,
intuitiveness
and
Owing to their robustness to local optima,
widespread coverage and high degree of
accuracy, multi-robot systems (MRS) are
highly efficient in the tasks of space exploration
and searching in unknown environments. There
have been numerous works in which MRS was
used to detect fire, pollutant sources and odor
sources [1, 2, 3].
Among a variety of potential algorithms to
implement on MRS, Particle Swarm
Optimization (PSO) has become a natural
choice for MRS in searching tasks. PSO was
first introduced by Russel Ebenhart and James
Kennedy in 1995 [4] and has gained popularity
among bio-inspired heuristic algorithms
simplicity. Motivated by social searching
behavior of natural swarm, PSO is especially
effective in optimization problems and widely
applied in various fields. Searching tasks of
MRS are in fact optimization problems, in
which the robots attempt to locate the regions
or spots of extreme signal intensity.
Although the idea of applying PSO to
multi-robot search is not novel, many problems
still need to be addressed adequately in order to
put that idea into practice. Some of them are
proneness to collision and premature
convergence. Many of the related works are
concerned with improving performance of the
MRS. In [5], the authors concentrated on
adjusting learning parameters for better results.
_______
1 This work is dedicated to the 20th Anniversary of the IT
In [6] the PSO algorithm was applied to model
multi-robot search and the effects of system
Faculty of VNU-UET
* Corresponding author. E-mail.: quyha@vnu.edu.vn
parameters were also evaluated. In [7], Doctor
1
2
H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10
et
al.
proposed
a
two
PSO
loops
model
to
deployment of robotic systems, flame detection
control their robot system. The inner loop was
or optical wireless charging.
applied for
collective
robotic
search and
the
The
methodology
and
simulation
are
outer was used to optimize quality parameters
discussed in detail in part 2, the results and
of
the
inner.
In
[8],
Cai
et.
al.
proposed
a
discussions
follow
in
part
3.
Finally,
part
4
potential
field-based
PSO
algorithm
for
concludes this paper with main conclusions and
cooperative
multi-robots
in
target
searching
directions for further research.
tasks. The problem of premature convergence,
which may adversely affect performance of
2. Methodology and simulation
PSO, was addressed in [9], where Nakisa et. al.
applied a method based on PSO and Local
2.1. Methodology
Search. In spite of various works on
application of PSO for MRS in the tasks of
exploration or searching in unknown
environments, there has not been a standard
approach with optimal result. All of the PSO-
based algorithms still need further experiments
and improvements.
In this paper, we present another approach
and a specific application: detecting light
sources or in other words, searching for the
brightest region in a search space. This method
is then compared with one of those mentioned
above. In our simulations, an MRS is
successfully used to detect light sources (by
gathering all the swarm robots around the area
of highest luminance in the search space). In all
scenarios, each robot (or particle as described in
PSO) has to move towards the mutual target
and meanwhile avoid obstacles. For the robot
swarm to exhibit this behavior, we modified
PSO algorithm by associating each particle with
an artificial potential field (APF) that can exert
repulsive forces to any other particle if their
distance is less than a predetermined value
called repulsive radius. This method of
avoiding collisions is inspired by APF
algorithm, which was proposed by Oussama
Khatib in 1986 for single robot path planning
[10]. APF is widely used nowadays in works on
MRS that demonstrate the interaction between
robots and obstacles in their work space [11].
The proposed PSO algorithm is named APSO,
its details will be presented in the next sections.
The simulation in Matlab shows reliable and
promising results, which could be applied in
various further applications such as dynamic
2.1.1. Artificial Potential Field
The APF model is inspired by Artificial
Physics with quadratic function, where the
choice of coefficients is commensurate to the
wireless sensor network of MRS. Myriads of
architectures for APF have been developed in
accordance with users’ definitions and specific
tasks, e.g. deploying mobile sensor networks in
unknown environment [12], controlling and
coordinating a group of robots for cooperative
manipulation tasks [13] or maintaining
connectivity of mobile networks [14]. In any
architecture, magnitude of the potential force
existing around each robot is continuously
updated based on information collected from its
immediate surrounding environment and other
robots via connection network. Therefore, APF
is used to regulate the relation between robots
in term of position. Potential force is
categorized into two main groups: passive force
and active force. Passive force is generated
when robot emit signal and determine distance
to neighboring robots or obstacles by the
magnitude of reflected signal to avoid obstacle
or remain relative position with other robots.
The signal used in the application could be
infrared, ultrasound, laser or camera [15]. On
the contrary, active force is generated from
external signals. These signals are usually
emitted by other robots and transmitted via
communication system [11]. In this research,
APF is only utilized for the purpose of collision
avoidance and only generates repulsive forces
on other particles within repulsive region, as
defined in this formula:
r
r
r
å
a
H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10
3
FAPFij = (Fmax k ij2) ij (1)
ij
where Fmax and k are predetermined constants to
regulate the magnitude of potential force, FAPFij
is the APF force exerted on robot i by robot j. rij
is the end-to-end distance vector from robot j to
robot i. rij is the module of rij.
Total force exerted on i-th robot of the
system is:
N
FAPFi = FAPFij (2)
j=1
where N is the number of robots, FAPFij is zero
if i = j. The impact of FAPFi on overall velocity
is controlled by Fmax and k. As Fmax increases,
the particle is less likely to approach obstacles.
In subsection 2.1.2, this will be discussed
further.
and particles’ positions are updated with the
following formulae:
vinertial = w´ vt- 1 (3)
vcognitive = 1´ u1´ j (pt- 1 - xt- 1) (4)
vsocial = a2 ´ u2 ´ j (gt- 1 - xt- 1) (5)
vt = vinertial + vcognitive + vsocial (6)
xt = xt- 1 + vt (7)
where:
vt: velocity of the swarm at t (time)
w: inertial factor
a1 : cognitive coefficient
a2 : social coefficient
u1 : random number in [0, 1]
u2 : random number in [0, 1]
2.1.2 APSO for MRS
The main contribution of this paper is to
propose and evaluate the efficiency of APSO, a
modified PSO algorithm. In this subsection, we
pt: personal best positions at t
gt: global best positions at t
xt: position of the swarm at t
φ(x): a matrix function that returns a row
briefly
present
principles
of
PSO
and
then
vector with each element being Euclidean norm
explain APSO in detail.
of
corresponding
column
in
the
matrix
In
PSO,
the
swarm
consists
of
argument.
homogeneous particles that can explore
search space collectively. During
the
the
In (4), φ(pt-1 xt-1) returns a vector. Each
element of this vector is distance from a
exploration,
the
movement
of
a
particle
is
corresponding particle to its own best position.
controlled
by
a
velocity
comprised
of
three
It is noteworthy that both position and velocity
components:
inertial,
cognitive
and
social
are vectors, so in the step of updating position,
velocity. Cognitive velocity leads the particle
they are added
directly to get
new position,
towards its personal best position and social
without any dimensional conflict.
velocity leads the particle towards the global
To apply PSO to an MRS, each robot is
best.
Inertial
velocity
guides
each
particle
modelled as a particle of the swarm and their
towards their previous directions and thus keeps
movements in the search space resemble those
particles’ movement smooth [16]. Besides, high
of
ideal
particles
described
above.
Actual
inertial velocity and cognitive velocity at initial
implementation
of
PSO
for
MRS
involves
steps make the swarm discover search space
additional techniques to solve problems which
better.
The
social
learning
factor
should
be
are
not
covered
in
its
conventional
version,
increased
and
cognitive
factor
should
be
such as collision avoidance. APSO is developed
decreased throughout the exploration in order to
to solve that problem. The steps in APSO are
enlarge the swarm’s coverage at initial steps
basically the same as those of PSO, but the
and make it converge faster at final steps. The
velocities and positions are updated with APF-
searching process using PSO is implemented in
based formulae. Artificial potential fields are
four stages: initializing, updating best positions,
also created around every particle in the search
updating
velocity
and
position,
and
finally,
space. The repulsive force between a particle
checking for stopping criteria. PSO velocities
and another particle or an obstacle is given by:

Swarm Optimization Approach for Light Source Detection by Multi-robot System

Đăng ngày | Thể loại: | Lần tải: 0 | Lần xem: 0 | Page: 10 | FileSize: M | File type: PDF
0 lần xem

Swarm Optimization Approach for Light Source Detection by Multi-robot System. In this paper, a modified Particle Swarm Optimization Algorithm (PSO) was presented for MRS on detecting light sources, namely APSO. In the proposed algorithm, an integration of conventional PSO and Artificial Potential Field (APF) is employed to use swarm intelligence for space exploration and light source detection.. Cũng như những giáo án bài giảng khác được thành viên giới thiệu hoặc do sưu tầm lại và giới thiệu lại cho các bạn với mục đích học tập , chúng tôi không thu phí từ bạn đọc ,nếu phát hiện tài liệu phi phạm bản quyền hoặc vi phạm pháp luật xin thông báo cho website ,Ngoài tài liệu này, bạn có thể tải bài giảng,luận văn mẫu phục vụ tham khảo Có tài liệu download thiếu font chữ không hiển thị đúng, thì do máy tính bạn không hỗ trợ font củ, bạn download các font .vntime củ về cài sẽ xem được.

Nội dung


1134915

Tài liệu liên quan