alexa The Algorithm of Distributed Survey Unknown Area | OMICS International
ISSN: 2090-4908
International Journal of Swarm Intelligence and Evolutionary Computation
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

The Algorithm of Distributed Survey Unknown Area

Sergey Norseev* and Dmitry Bagayev

Kovrov State Technological Academy named after V.A. Degtyareva, Kovrov, Russia

Corresponding Author:
Sergey Norseev
Kovrov State Technological Academy named after V.A. Degtyareva
Kovrov, Russia
Tel: 79607218811
E-mail: [email protected]

Received date: January 01, 2014; Accepted date: April 30, 2014; Published date: May 30, 2014

Citation: Norseev S and Bagayev D (2014) The Algorithm of Distributed Survey Unknown Area. Int J Swarm intel evol comput 3:108. doi:

Copyright: © 2014 Norseev S, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Visit for more related articles at International Journal of Swarm Intelligence and Evolutionary Computation

Abstract

 In this paper we propose a distributed algorithm for the survey of unknown area, with help of a group of mobile robots. We also describe the architecture of an application developed to test the effectiveness of the proposed algorithm.

Keywords

Robotics; Group management

Introduction

The problem of finding and deactivating mines in a minefield, search and evacuation of injured men from the disaster area, conducting anti-terrorist operations (the list goes on) resolve itself to the study area. It is reasonable to use robotic systems for solve these problems, because the solving can be hazardous job. If the size of the study area is large, it is necessary to use a group of interaction robots.

In this paper propose a distributed algorithm for a group of mobile robots to explore an unknown area with some obstacles.

Purpose of this researching is development algorithm for a group of mobile robots to explore an unknown area.

Problem Definition

There are boundary area S and group, consists from N mobile robots. In the area there are K arbitrary shape obstacles. R = {r1, r2, r3,…, rN} is a set of mobile robots, P={p1,p2,p3,….,pK} is a set of obstacles.

Let equation denote coordinates of i-th robot center. In case of moving robot, its position is a time function: equation Every robot have own boundary visibility scope Vi. Assume visibility scope have the form of circle of radius Rv. Center of this circle same as center of mobile robot. For i-th mobile robot visibility scope follows the formula:

scope follows the formula:

equation Visibility scope is a time function: equation Understandably, that: V =V1 ∪V2 ∪V3 ∪........VN ⊆ S

However, there is area D: D = {(x, y) ∈ S\V}

And D ≠∅

D is the “blind” area. Nothing “see” this area. “Blind” area of group is a result of crossing of robot “blind” areas:

D = D1∩D2 ∩D3 ∩...∩DN

Position of “blind” area is time function:

D = f D(t)

And:

D = f D(t) = S\(fV1 (t) ∪ f V2 (t) ∪ f V3 (t) ∪..... ∪ f VN (t))

In fact, position and size of “blind” area are the function of robot moving.

Let D’ denote area, which is “blind” area for long period of time:

D = {(x,y) ∈ f D (t) |t = t0,t1}

t0 and t1– are some points in time.

Need search the function equation such that D’= ∅. It is necessary to take into account the following circumstances.

Number of robots maybe various.

The possibility of breakage of certain robots. Break robot can’t move and “see” nothing, so: Vj = ∅.

Some object (name it a “bonus”) may be located in the area S. This object should be founded by robots. Let (xB,yB) denote coordinates of “bonus”.

Nature of “bonus” depends up the problem solving by robots. If robots searching and deactivating mines, then “bonus” can be mine. If robots searching injured men, then “bonus” can be injured man, and so on.

Moving of certain robot must be requirements.

Possibility of work in unknown environment.

Independence from other robots. Robot don’t “know” about other robots.

Collision avoidance with obstacles (if any).

Collision avoidance with other robots (if any).

Finding of “bonus” (if any).

i-th robot found “bonus”, if this”bonus” located in robot visibility scope. In other words, robot found “bonus”, if condition is true.

equation Formulate main requirements to the algorithm.

1. Applicability for various numbers of robots.

2. Possibility work in unknown environment.

3. Possibility finding “bonus” in the area S.

4. Interchangeability robots. All robots must have similar logic of work:

f r1(t) ~ f r2(t) ~ f r3(t) ~ ……..~ f rN(t)

Existing approaches to solving the problem

Area S decomposed into several small zones in most cover algorithms. But the decomposition into zones is carried out in different ways.

In the paper [1] use Lloyd algorithm. This algorithm bases on the construction and improvement of Voronoi diagram [2]. This algorithm can’t use for unknown area.

In the paper [3], the rectangular net is applied over the whole area. The area is represented as a two-dimensional array of zones. We will use this method.

Decompose area

Decompose area S into L rectangular zones. Let s = {s1, s2, s3,……….. sL} denote set of zones.

Number of zones depends up zone size and area size.

Zone size is chosen based on the ability certain robot, area size, the required accuracy of the mapping (if there is such task).

If the zone size exceeds visibility scope size of certain robot, the robot can’t “see” whole zone. Let equation denote size of i-th zone. It must satisfy the condition: equation Small zone size leads to the drawing of a more accurate map of the study area, but increases the total number of zones.Introduce for each zone validation counters ci. This number indicates how many times this zone was validated by some robot. Robot validated zone, if it could come to center of this zone. Thus zone validation counter is incremented. Let equation denote coordinates of i-th zone center.

If robot can’t come to zone center, because it interferes with the obstacle (and can’t go around an obstacle without going beyond the limits of the zone), consider this zone is “occupied” zone as shown in Figure 1.

Figure

Figure 1: Correspondence size zone and radius of visibility scope.

Robot movement

Every time, the robot strives to reach the center of the next target zone. The direction of the robot movement is calculated by following formula:

equation Where: ri(t) – movement vector of i-th robot at a time t;

(xi(t);yi(t)) – Coordinates of i-th robot at a time t;

equation – Coordinates of new target zone center for the i-th robot at a time t.

When the robot came to zone center, it increment validation counter of this zone and choose new target zone;

Choosing of target zone is carried out either by the robot, based on available information about area (in the case of a decentralized architecture) or the control center (in the case of a centralized architecture). In the second case, robot report fact of zone validation to control center and request new target zone.

As a new target zone choose zone, adjacent to current zone of the robot, having the smallest number of validations.

Program implementation of the algorithm

For test proposed algorithm we developed special program in C++ Builder as shown in Figure 2. This program show surveying unknown area by group of robots. Below are the main features offered by the program.

Figure

Figure 2: General scheme of the proposed algorithm.

Set obstacles, having various form.

Set “bonus” in the various point of the area.

Simulate a break of the robot.

Simulate a fix of the broken robot. This fixed robot return to the group of robots.

Describe every class from the UML diagram as shown in Figure 3.

Figure

Figure 3: UML diagram of the application classes.

T MainForm – class of dialog window. It interact with user and receive commands from one.

Agent – class of mobile robot. For every robots stored following information: current position (“X” and “Y” members), coordinates of the target zone center (“TargetX” and “TargetY” members), the flag of robot failure (“IsBroken” member) and the flag of founded “bonus” (“FindBonus” member). At each step called method Step(). It implement the algorithm, shown in the picture 2. Draw() method draw robot on the window TMainForm. Break() method simulate robot failure. Fix() method simulate fixe of the broken robot.

swarm –class-container for robots _Agent. _swarm class store number of robots (Count Agents member) and the array of robots. _swarm class methods call correspond _Agent class methods. Break Random Agent () method random choose the robot and call Break () method of it. Fix Agent () method find first broken robot and fix it. Step () method sequential call Step () method of every robot.

Zone – structure, storing information about certain zone. It stores following information: center zone coordinates (“cX” and “cY” members), flag of occupied zone (“is Occupy” member); and zone validation counter (“CpoountVisits” member).

Area – class-container for the set of zones s. It store: number of zone (“Count Zones” member) and array of zones. Check Zone () validate zone and increment validation counter of this zone. Set Occupy Zone () method set flag “is Occupy” of the zone. Get Target Zone () method choose new target zone for the robot.

The program affirmed the applicability of the proposed algorithm.

Conclusion

Developed algorithm of distributed survey unknown area by mobile robots group.

Developed program affirmed the applicability of the proposed algorithm.

References

Select your language of interest to view the total content in your interested language
Post your comment

Share This Article

Relevant Topics

Recommended Conferences

  • 5th International conference on Artificial Intelligence
    April 16-17, 2018 Las Vegas, USA
  • 5th International Conference on Automation and Robotics
    April 16-17, 2018 Las Vegas, USA
  • 4th Global Summit and Expo on Multimedia & Artificial Intelligence
    July 19-21, 2018 Rome, Italy
  • International Conference on Artificial Intelligence, Robotics & IoT
    August 21-22, 2018 Paris, France
  • 6th World Convention on Robots and Deep Learning
    September 10-11, 2018 Singapore City, Singapore
  • International Conference on Mechatronics & Robotics
    October 15-16, 2018 Helsinki, Finland

Article Usage

  • Total views: 11586
  • [From(publication date):
    September-2014 - Feb 25, 2018]
  • Breakdown by view type
  • HTML page views : 7833
  • PDF downloads : 3753
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

Peer Reviewed Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
International Conferences 2018-19
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri & Aquaculture Journals

Dr. Krish

[email protected]

1-702-714-7001Extn: 9040

Biochemistry Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

[email protected]

1-702-714-7001Extn: 9042

Chemistry Journals

Gabriel Shaw

[email protected]

1-702-714-7001Extn: 9040

Clinical Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Engineering Journals

James Franklin

[email protected]

1-702-714-7001Extn: 9042

Food & Nutrition Journals

Katie Wilson

[email protected]

1-702-714-7001Extn: 9042

General Science

Andrea Jason

[email protected]

1-702-714-7001Extn: 9043

Genetics & Molecular Biology Journals

Anna Melissa

[email protected]

1-702-714-7001Extn: 9006

Immunology & Microbiology Journals

David Gorantl

[email protected]

1-702-714-7001Extn: 9014

Materials Science Journals

Rachle Green

[email protected]

1-702-714-7001Extn: 9039

Nursing & Health Care Journals

Stephanie Skinner

[email protected]

1-702-714-7001Extn: 9039

Medical Journals

Nimmi Anna

[email protected]

1-702-714-7001Extn: 9038

Neuroscience & Psychology Journals

Nathan T

[email protected]

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

Ann Jose

[email protected]

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

[email protected]

1-702-714-7001Extn: 9042

 
© 2008- 2018 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version