I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   7 ,   No .   1 ,  Feb r u ar y   201 7 ,   p p .   3 9 2 ~ 4 0 1   I SS N:  2088 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 7 i 1 . p p 3 9 2 - 4 0 1           392       J o ur na l ho m ep a g e :  h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I JE C E   O ff ine/ O nline  O p ti m u m  Rou ting o f  a UAV   u sing   Au x ilia ry   Points       Abba s   F a da v i 1 ,  Ali B ehesh t i 2 ,  P edra m   K er m a ni 3   1 De p a rtme n t  o f   M e c h a tro n ics ,   S c ien c e   a n d   Re se a rc h   Bra n c h ,   Isla m ic Az a d   Un iv e rc it y ,   S e m n a n ,   Ira n   2 S c h o o l  o f   El e c trac a l  En g in e e rin g ,   Ira n   Un iv e rsity   o f   S c ien c e   a n d   T e c h n o l o g y ,   T e h ra n ,   Ira n   3 D e p a rtme n   o f   El e c tri c a l  a n d   Co m p u ter E n g ,   A b b a sp o u r   Co ll e g e   o f   En g in e e rin g   S h a h id Be h e sh t i  U n iv e rsity ,   A C. ,   T e h ra n ,   Ira n       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   J u l 8 ,   2 0 1 6   R ev i s ed   Oct   2 1 ,   2 0 1 6   A cc ep ted   No v   5 ,   2 0 1 6       T h is  p a p e r  p re se n ts  a   m e th o d   to   d e term in e   th e   ro u te  o f   a   th re e - d ime n sio n a l   UA V .   T h re e   c rit e ria;  th e   h e ig h t,   t h e   len g th   o f   fl ig h t  p a th   a n d   t h e   u n   a u th o r ize d   a re a s  a re   u se d   a s  th e   c o n stra in ts  a n d   c o m b in e d   i n   a   f u z z y   f u n c ti o n   a s  th e   e v a lu a ti o n   f u n c ti o n .   T h e   a rti c le  a i m e d   to   d isc o v e r  a   m in im u m   c o s t   ro u te  f ro m   so u rc e   to   d e sti n a ti o n   c o n si d e rin g   t h e   c o n stra in s.   In   t h is  p a p e r  a   n e w   s e a rc h in g   m e th o d is  p r o p o se d ,   w it h   u se   o f  a u x il iar y   p o in ts.   T h e   a u x il iar y   p o i n t  m e th o d   i tera ti v e l y d iv id e s  a   stra ig h t  li n e   t o   tw o   sh o rter  li n e s  w it h   les s  c o st  o f   e v a lu a ti o n   f u n c ti o n .   Im p l e m e n tatio n   re su lt s  s h o w   th a t  t h e   p ro p o se d   m e th o d   d ra m a ti c a ll y   d e c re a se sth e   c a lcu latio n s;  m e a n w h il e   th e   ig h t  ro u t e   is   su b - o p ti m u m .   K ey w o r d :   E v alu a tio n   Fu zz y   s y s te m s   T h r ee - d i m en s io n al  r o u tin g   UAV   Co p y rig h t  ©   2 0 1 7   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   A b b as Fad av i ,    Dep ar t m en t o f   Me ch atr o n ics ,   Scien ce   a n d   R esear c h   B r an ch ,     I s la m ic  A za d   U n iv er ci t y ,   Se m n an ,   I r an   E m ail: a b b as_ f ad a v i@ y a h o o . co m       1.   I NT RO D UCT I O N   UV A   h a s   it s   ap p licatio n   m a in l y   i n   t h e  m ilit ar y   i n d u s tr y   [ 1 - 3 ] .   Ho w e v er ,   it  is   u s ed   in   a  lar g e  n u m b e r   o f   n o n - ci v ilia n   ap p licatio n s ,   s u ch   a s   f ir e  f ig h ti n g ,   m eteo r o lo g y ,   ae r ial  p h o to g r ap h y   an d   r es ea r ch   p r o j ec ts .   T h e  ai m   o f   th is   ar ticle  is   to   d is co v er   an   ap p r o p r iate  r o u te  f o r   th e  UAVs.  A n   o p ti m u m   r o u te  is   a  m in i m u m   d i s tan ce   r o u te  o n e  w h ic h   b est  s ati s f ie s   th e  co n s tr ai n t s .   Dif f er en t  m et h o d s   h a v e  b e en   in tr o d u ce d   an d   d is cu s s ed   in   o r d er   to   d eter m i n e  t h e  o p ti m a l  au x il iar y p o in ts .   Var io u s   ar ticle s   h a v e  b ee n   p r ese n ted   to   d eter m in e  th e  o p ti m a l  r o u t e   f o r th e  UV As.  A   n u m b er   o f   th ese  ar ticles  h a v e  m ad e  u s e  o f   class ic  m et h o d s .   Fo r   ex a m p l e   [ 4 ]   an d   [ 5 ]   u s e  A  f o r   t h e  p u r p o s e  o f   s ea r ch in g ,   w h ile  [ 6 ]   u s es  T eta  an d   D.   ( A ,   T eta  an d   D  s h o u ld   b e  d ef i n ed ) .   Sev er al  ar ticles  h av e  u s ed   ev o l u tio n ar y   al g o r ith m s   in   o r d er   d is co v er   t h e  r o u te  [ 7 ] .   A r ticle  [ 8 ]   to o k   a d v an ta g e  o f   P SO,     ar ticle  [ 9 ]   u tili ze d   GA   an d   ar ticle  [ 10 ]   u tili ze d   GSO.   Qu e  et  al.   [ 1 1 ]   ap p lied   h ier ar ch ical  d ec is io n   m a k i n g .   T h eir ,   th e  i n te n d ed   en v ir o n m en t  w a s   f i r s t  e x a m in ed   a n d   d i v id ed   in to   d if f er en t  ar ea s .   T h en ,   ac co r d in g   to   t h e   r ate  o f   th e  co n s tr ai n ts   s at is f a ct io n   p r o b lem s ,   t h e  b est  id en ti f i ca tio n   ar ea s   an d   th e  p at h s   w er e  s p ec if i ed   in o r d er   to   b e  ab le  to   r ea ch   th e  d est in a tio n   f r o m   t h e  s o u r ce   a m o n g   o p ti m u m   zo n esa n d   to   d is co v er   th e  b est  p at h .   T h e   m et h o d   o f   Dij k s tr a  w as  u s ed .   R o b er g ee tal  [ 1 2 ]   p r esen ted   a  d e fi n ite  co s t  f u n c tio n .   T h is   f u n ctio n   u tili ze d   a  co m b i n atio n   o f   d i f f er en t  co n s tr ai n ts   li k e  d is ta n ce   len g t h   w ith   d an g er o u s   p o in ts   an d   th e  r ate  o f   f u el   co n s u m p tio n .   T h en ,   th e  o p ti m al  p ath   w as  ca lc u lated   u s in g   g en etic  alg o r it h m s   o r   P SO  b ase d   o n   m i n i m izi n g   o r   m ax i m izin g   t h e  co s t  f u n c tio n .   A l s o ,   r esear ch er s   li k e   Ko k   et  al   [1 3 ]   ap p lied   ex ec u ti v e  p o in t s   to   th eir   h ar d w ar e   r o u tin g   i m p le m en ta tio n .   I n   a r t icle  [ 1 1 ]   th e  en v ir o n m e n t  w a s   f i r s t   ex a m i n ed   an d   d i v id ed   in to   d if f er e n t  zo n e s .   T h en ,   o p ti m al  zo n e s   w er e  id e n ti f i ed .   T h ese  ar e  t h e  zo n es   wh ich   b etter   s ati s f i ed   th e   p o in ts   in s id e  th e  zo n es  o f   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2088 - 8708     O ff in e/On lin e  Op timu m  R o u tin g   o f a   UA V   Usi n g   A u xilia r y  P o in ts   ( A b b a s   F a d a vi )   393   co n s tr ain ts .   Nex t,  s p ec i f i c  r o u tes  w er eselecte d   f r o m   t h e  s o u r ce   to   d esti n atio n   th r o u g h   o p tim a l  zo n es.  T o   d iag n o s e  t h e   b est   r o u te,   th e   m et h o d   o f   Dij k s tr a  w a s   ap p lied .   A r ticle  [ 1 2 ]   p r o v id ed   th e  ce r tain   p er f o r m a n ce   f u n ctio n .   I t  u tili ze d   a  co m b i n a tio n   o f   v ar io u s   co n s tr ai n ts   s u c h   as   d an g er o u s   s p o ts   alo n g   t h e   r o u te  d is tan ce   an d   f u e l c o n s u m p tio n   a m o u n t; Fo l lo w ed b y   t h e  d is co v er y   o f   t h e  o p tim a l r o u tes b y   u s i n g   th is   p er f o r m an ce   f u n ct io n   w it h t h e  aid   o f   P SO  a n d   G A .   A r ticle   [ 1 3 ]   ex p lain ed   t h e  i m p le m e n tatio n   o f   a  r o u tin g   m et h o d   o n   th e  h ar d w ar e.   T h e  s ec o n d   s ec tio n   p r ese n ts   d ef i n itio n   o f   t h e  p r o b lem a n d   o u r   m at h e m atica l  ap p r o ac h   to   s o lv in g   t h e  p r o b le m .   T h en ,   th eir   co n s tr ai n ts   ar e  e x a m i n ed .   T h e  th ir d   s ec tio n   p r es en ts   th e  p r o p o s ed   m et h o d   an d   d escr ib es  d if f er en t   m et h o d s   u s e f u l  in   t h e  d is c o v er y   o f   th e  s u i tab le  au x il iar y   p o in t.  T h e  f o u r th   s ec t io n   p r esen ts   t h e   i m p le m en ta tio n   r es u lts .   T h e  ar ticle  is   co n cl u d ed   in   th e  e n d   o f   th e  ar ticle.       2.   DE F I N I T I O N  O F   T H E   P R O B L E M   AND  T H E   E VA L U AT I O N  F UN CT I O N   T h e  p r o b lem   o f   d is co v er i n g   t h e  r i g h t  w a y   to   m o v e  a  UAV  is   an   is s u e  w i th   a  lo t  o f   in p u t  p ar am eter s   an d   th e  an s w er   is   n o t  u n iq u e.   T h er ef o r e,   th is   p r o b lem   m u s t  b e  s o lv ed   u s in g   m at h e m atic al  m o d elin g   o f   t h e  ef f ec tiv e  p ar a m e ter s   to   ch o o s e  th e  p ath .   I n   t h is   p r o b le m ,   s in ce   it  is   i m p o s s ib le  to   p as s   th e  n at u r al  an d   s y n t h etic  o b s tacle s ,   v er y   lo w   o r   v er y   h ig h   altit u d e  ar ea s   an d   u n a u t h o r ized   ar ea s ,   s o m e  d ec is io n s   ar e  co n s id er ed   as  co n s tr ain s   wh ile  o t h er   d ec is io n   p ar a m et er s   ar e  co n s id er ed   as  an   e v alu a tio n   f u n ct io n .   P r ac tically ,   t h e  p r o b lem   o f   d eter m i n i n g   t h e  o p ti m al  r o u te  b ec o m e s   th e  m ath e m at ical  m ax i m izin g   o r   m i n i m izi n g   o f   th e  o b j ec tiv e  f u n ct io n   w it h   r esp ec t  to   t h e  p r ed ef in ed   co n s tr ain s .   T h e  s ele cted   r o u te  in v o lv es   th e  d eter m in at io n   o f   t h e  p o in ts   ( th e   len g t h ,   w id t h   a n d   h e i g h t   o f   ea c h   p o in t) ,   b eg i n n i n g   f r o m   th e   p o in t  o f   o r ig in   a n d   en d i n g   w it h   t h e  p o in t  o f   d esti n atio n .   I n   t h i s   p ap er ,   th e  s p ee d   o f   a ir cr af t  m o v e m en t  i s   co n s tan t  an d   th e  p ath   i s   d eter m i n ed   w a s   d eter m in ed   i n d ep en d en tl y   o f   s p ee d .   T h e  in ten d ed   p r o v is io n s   o f   t h e  ar ticle   co n tain ed   h e ig h t,  le n g t h   a n d   u n au t h o r ized   ig h t r eg io n s .   On e  o f   t h e   s o lu tio n s   to   co v er   all  t h e  d ef i n ed   co n s tr ai n t s   i s   t h e  u s e   o f   a  p h a s e  m ac h i n e  to   p r o d u ce   an   o v er all  i n d icato r .   I n   t h is   m eth o d ,   all  th e  in f o r m at io n   o f   t h e   d ef i n ed   en v ir o n m e n t  to   cr o s s   an d   u n au th o r ized   ar ea s   to   fl y   ar e  g i v en   to   t h e   p h ase m ac h i n e.   T h is   p h ase  c ar   p r o d u ce s   an   in d icato r   f o r   ea ch   p o in t  o f   th e   en v ir o n m e n t  w h ic h   i s   ca lled   t h e  d esira b le  p ass   i n d icato r .   I t  co v er s   all  t h e  d ef i n ed   co n s tr ai n ts   o f   t h e  p r o b lem .   T h e  m o d el  o b tain ed   f r o m   t h e  f u zz y   m ac h i n e  is   ca lled   a  p h ase  m ap .   T h e  aim   i s   to   o b tain   a  r o u te  th at  b etter   s atis f i es t h e   d esire d   p ass   i n d icato r .   T h e  m o d eli n g   o f   [ 1 4 ]   is   ad o p ted   in   th i s   ar ticle  i n   w h ic h   t h e  af o r e m e n tio n ed   t h r ee   co n s tr ain ts   h a v e  b ee n   m o d eled   w it h   th e  p h as e  m ac h i n e.   T h e  p r esen ted   m o d el   s p ec if i e s   th e  p er f o r m a n ce   f u n ctio n   o f   t h e   p r o b l em .   T h is   f u n ctio n   is   ab le  to   r ec eiv e  th e  p o s itio n   o f   an y   p o in t  in   t h e  en v ir o n m en t  a n d   p r o v id e  a  ce r tain   a m o u n t   a s   e f f icien c y .   A   s p ec if i ca tio n   o f   th e   li n e  b et w ee n   th e  s tar tin g   a n d   d esti n atio n p o in t  a s   t h e  p ass in g   r o u te  w a s   ai m ed   at.   T h is   li n e  co n s is ts   o f   p o i n ts .   T h e  p o s itio n   o f   p o in ts   i s   p lace d   in   t h e  p er f o r m a n ce   f u n ctio n .   T h e  to tal  o f   o b tain ed   am o u n t  o f   th e  p er f o r m a n ce   f u n ctio n   o f   p o in ts   o f   a  lin e  s h o w s   t h e  p er f o r m an ce   a m o u n t   o f   th e  li n e.   T h e  r o u te  b et w ee n   th e  s o u r ce   an d   d esti n atio n   i s   o p ti m al w h en   t h e  p er f o r m a n ce   f u n ctio n   is   m u c h   less ,   w h ich   ad h er es b etter   to   th e  co n s tr ai n t s .   T o   s ea r ch   th e   o p ti m u m   p o i n ts   o f   th e  r o u te  d if f er e n t  s ea r c h i n g   m et h o d s   m i g h tb e  u s ed .   T w o   r ec en t l y   p r o p o s ed   m et h o d s ,   w h ic h   w e  w il l  co m p ar e  o u r   m e th o d   w ith   th o s e,   ar e  th e  p ar ticle  s w ar m   o p tim izatio n   ( P SO)   is   u s ed   i n   [ 8 ] ,   an d   th e G A   [ 1 4 ] .   T h is   co m p ar is o n   i s   o n   t h e  b a s is   o f   t h e  ca lcu la tio n   ti m e  a n d   b etter   d ir ec tio n   i n   r eg ar d   to   f u zz y   m ap .       3.   T H E   O F F E R E D  M E T H O D   T h is   s ec tio n   p r ese n ts   a  m et h o d   to   d is co v er   an   ap p r o p r iate  r o u te  b et w ee n   t h eso u r ce   an d   d esti n a tio n .   Fig u r e  1   s h o w s   a  s a m p le  f u z z y   m ap   o f   a n   e n v ir o n m e n t,  i n w h ic h   ea ch   p o in t  o f   t h e  m ap   b elo n g s   to   a  f u zz y   f u n ctio n .   T h e  co n s tr ai n ts   ar ein s er ted   to   a  f u zz y   f u n cti o n .   Dar k   b l u e  r eg io n s   ar e  p r ef er r ed   ar ea   w it h   m i n i m u m co s t  a n d   m a x i m u m   p er f o r m a n ce   a n d   th e  r ed   r eg io n s   b elo n g   to   n o n - a u t h o r ized   ar ea s   w i th   m ax i m u m   co s t  an d   m in i m u m   p er f o r m a n ce .   I n   Fig u r e  1   p o in t  A   is co n s id er ed   as  th e  s o u r ce   an d   p o in t  B   as  th e   d esti n atio n .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 ,  Feb r u ar y   201 7   :  3 9 2   –   401   394       Fig u r e  1 .   A   h y p o th et ical  en v ir o n m e n t i n d icatin g   s tate m e n t o f   th e  p r o b le m   A ,   So u r ce   B   an d au x i liar y   p o in t M       3 . 1 .   Dec is io n - M a k ing   Reg a rding   t he  Alt er na t iv e  Ro ute   I t  is   a  k n o w n   f ac t  t h at  t h e  clo s est  p ath   b et w ee n   t h e  t w o   p o in ts   o f   A   an d   B   is   t h e  s tr ai g h t   lin e  A B .   T h er ef o r e  lin e  A B   is   th e  s h o r test   p ath   b et w ee n   A   an d   B .   B u t  as  s h o w n   i n   th e  f ig u r e,   lin e  A B   p ass es  t h r o u g h   an   ar ea   w i th   p o o r   co n d itio n s .   A  p ath   w h ic h   is   to o   s h o r t  a n d   d o es  n o t  p a s s   t h r o u g h   d i f f ic u lt  ar ea s   i s   r eq u ir ed .   T h e  p o in t  n a m ed   M   is   co n s id er ed   as  an   au x iliar y   p o in t.  T h e  lin e   A M  a n d   MB   ar e  co n n e cted   w ith   t h e  t wo   p o in ts   A   an d   B .   T h is   d ir ec tio n   is   lo n g er   t h an   A B ,   b u t d o es n o t p ass   th r o u g h   a  d i f f ic u lt a r ea .   I f   F   is   a  co s t   f u n ctio n   an d   F AB   th e  co s t   o f   A B   d ir ec tio n ,   I f   F A B   >  F AM   +FM B   T h e n   t h e  p o in t  M  i s   a  g o o d   p o in t  b ec au s e  it  co u ld   h elp   o p ti m ize  t h e  co s t   f u n ctio n .   B u t  i f   F A B   <  F A M  +F MB   T h en   th e  p o in t  M  is   n o t  a  g o o d   p o in t  b ec au s e  t h is   co u ld   n o t  o p ti m ize  t h e  co s t  f u n ctio n .   T h e   p er ce n ta g e  o f   co s t  f u n ct io n   im p r o v e m en t b y   th e  a u x iliar y   p o in t is ca lled   OP T   an d   its   r el atio n   is   e x p lain ed   as  f o llo w s :                                        I n   th i s   r elatio n ,   A ,   B   an d   M  a r e  s o u r ce ,   d esti n atio n   an d   a u x iliar y   p o in t,  r esp ec ti v el y .   I f   O PT   >  0 ,   M   is   t h e  p r o p er   au x iliar y   p o in t   a n d   if   OP T   <   0 ,   th e  au x iliar y   p o in t  d o es  n o t  ac t  h elp f u ll y   a n d   o n l y   le n g t h en s   t h e  r o u te.   I f   M   is   in   th e   li n e  A B ,   OPT   =  0 .   I t  s h o u ld   b e  n o ted   t h at  v ar io u s   co n s tr ain t s   ar e  a v a ilab le  in   th e   f i tn e s s   f u n ctio n ,   an d   d is tan ce   is   j u s t  o n e  o f   th e m .   Fo r   th is   r ea s o n ,   i n   s o m e  ca s e s ,   b r ea k in g   a  lin e  i n to   t w o   lin es  b y   t h e  au x i liar y   f u n ctio n   i n cr ea s es  t h e  d is tan ce   an d   d ec r ea s es  o th er   co n s tr ain ts   o f   t h e  f i t n es s   f u n ct io n .   He n ce ,   th e   a m o u n t  o f   t h e  to tal   f i t n ess   f u n ctio n   g e n er all y   d ec r ea s es   t h r o u g h   t h e  a u x iliar y   p o in t.  T h e  b asic  id ea   h er e   w a s   d er iv ed   f r o m   t h e  b eh a v io r   o f   a  h u m a n   w h e n   e n co u n ter in g   an o b s tacle .   A   h u m an   c h a n g es  d ir ec tio n   w h e n   f ac i n g   a n   o b s tacle   an d   tr ies  to   cr o s s   f r o m   o n e  o f   it s   s id es.   Ou r   p r o p o s ed   m et h o d   is   also   th e  s a m e  i s   h u m a n   d ec is io n   m ak i n g .   OP T   v alu e  i n d icate s   f e w er   co s ts ,   u s i n g   t h e  au x i liar y   p o in t.  I f   t h e  v al u ei s   less   th a n   ze r o ,   it  in d icate s   t h at  th e  s a m e  p r i m a r y   s tr aig h t  li n e  b et w ee n   th e  t w o   p o in ts   is   a  g o o d   w a y   a n d   th e  u s e  o f   a u x iliar y   p o in t d o es n o t i m p r o v e  th e  r o u te.   B y   b r ea k i n g   a  li n e  a n d   t u r n i n g   it   i n to   t w o   li n e s ,   an   a u x il iar y   li n e  w ill  lead   to   a  b etter   r o u te.   I n   t h e   s a m e  w a y ,   t h e  F u n ctio n   F  f o r   th e  t w o   o b tain ed   li n es   ca n   b e  p er f o r m ed .   B y   s o   d o in g ,   t h e  s t r aig h t  lin e   b et w ee n   th e  t w o   p o in t s   o f   s o u r ce   a n d   d esti n atio n   is   b r o k en .   T h en ,   t h ese  t w o   lin e s   ar e  co n v er ted   i n to   t w o   o th er   li n e s .   T h is   p r o ce d u r e  is   co n tin u ed   u n til  t h e  len g t h   o f   t w o   li n es  b e co m e s   m o r e  th a n   th e  m i n i m u m   a m o u n t.  Fi g u r e  2  in d icate s   th e  r e s u l t  f o r   th e  t wo   h y p o th e tical  p o in t s .   T h e  r o u te  b et w ee n   t h e  t w o   p o in t s   o f   A  an d   B   i s   d iv id ed   in to   au x iliar y   p o in ts .   I n   f ac t,   th ese  li n es,  w i th   t h e  h elp   o f   a  s lig h t  d ev ia tio n   i n   th e  r o u te,   en ab les  f o r   t h e   s atis f ac tio n   o f   t h e  e v al u atio n   f u n ct io n .   C las s ical   ar tific ial  in t ellig e n ce   m et h o d s   [ 1 5 ] ,   s o lv i n g   t h e  p r o b le m s   ar e   ca teg o r ized   to   b o tto m   to   to p   o r   to p   to   b o tto m   m eth o d s .   I n   th is   r esear c h ,   o u r   ap p r o ac h   is   to p   to   b o tto m .   T h is   i m p lies   t h at  t h e  f ir s t  i s s u e  w as   s p lit  in to   t w o   p ar ts ,   w it h   ea c h   p ar t  f u r t h er   d iv id ed   in to   s m aller   p ar ts .   Fig u r e  3  d em o n s tr ate s   h o w   th is   s ea r ch   o cc u r s .   Fi n d   P ath   f u n ctio n   ta k es  th e   p o in ts   o f   s o u r ce   an d   d e s tin a tio n ,   a n d   f i n d s   th e  n ec e s s ar y   a u x iliar y   p o i n ts .   First  b y   u s i n g   th e  f u n ctio n   Fin d   A cillar y   P o in t,  th e  a u x i liar y   p o in t  b et w ee n   t h e  s o u r ce   an d   d esti n atio n   is   d eter m in ed .   T h en   T h e  OPT   v alu e  is   ca lc u l ated .   A   lo w er   v al u e  o f   OP T   is   lo w er   t h an   th e   m i n i m u m   a m o u n t   in d icate s   t h at  b r ea k in g   t h e  s tr ai g h t   li n e  b e t w ee n   t h e  s o u r ce   a n d   d esti n ati o n   is   a   s i g n   o f   litt le   p r o f it.   T h er ef o r e,   th e   s a m e  s tr aig h t  li n e   b et w ee n   t h e  s o u r ce   an d   d esti n atio n   i s   a n n o u n ce d   as  a  d es ir ab le  r o u te.   Ho w e v er ,   if   t h e  a m o u n t  i s   m o r e  th a n   t h e  m i n i m a l  a m o u n t,  t h e  d ir ec t  li n e  b et w ee n   t h e  s o u r ce   an d   d esti n atio n   in to   t w o   l in e s   is   b r o k en   w i th   th e  h elp   o f   a u x iliar y   p o in t s .   I f   th e  len g t h   o f   ea ch   o f   th e  t w o   lin es  i s   m o r e  th a n   th e  m i n i m al  a m o u n t,  t h e  a lg o r ith m   ca n   b e  r ep ea ted   f o r   ea c h   o f   t h e   t w o   b r o k e n   l i n e s .   I n   f a ct,   th e  s tr ai g h t   li n e  b et w ee n   th e  s o u r ce   an d   d esti n atio n   ca n   b e  d iv id ed   in to   s u ch   p iece s   t h at  ar e  v er y   s m all,   an d   th e  b r ea k i n g   o f   th e  b en e f icia l  p ar ts   b ec o m es   u n n ec e s s ar y .   Fo r   ex a m p le,   in   Fig u r e  2 ,   p o in ts   A   a n d   B   ar e  s o u r ce   an d   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2088 - 8708     O ff in e/On lin e  Op timu m  R o u tin g   o f a   UA V   Usi n g   A u xilia r y  P o in ts   ( A b b a s   F a d a vi )   395   d esti n atio n ,   r esp ec ti v el y .   P o in t  M1   is   s elec ted   as   a n   a u x iliar y   p o in t  b et w ee n   t h ese   t w o   p o in ts .   A  p o in t   b et w ee n   M1   a n d   M4   is   s ele cted   as  t h e  au x il iar y   p o in t  b et w ee n   p o in ts   M1   a n d   A .   H o w e v er ,   n o   p o in t   is   s elec ted   b et w ee n   t h e  p o in t s   A  an d   M4   b ec au s e  t h e  s tr aig h t  l in e  b et w ee n   th e   t w o   p o in ts   is   s u itab le  e n o u g h .   I t   is   p o s s ib le  to   o b tain   an   a u x ili ar y   p o in t  th a t  r ed u ce s   t h e  co m p u tat io n al  co s t.  Ho w e v er ,   th e  i m p r o v e m e n t  i s   s o   lo w   t h at  it  ca n   b e  i g n o r ed   d u e   to   th e  co m p u tatio n al  co s t.  B et w ee n   p o in t s   M4   an d   M1 ,   M2   au x il iar y   p o in t  i s  s elec ted .   T h e  d is ta n ce   b et w ee n   t h e  t w o   p o in ts ,   M4   an d   M2 ,   is   s m a ll.  Fo r   t h i s   r ea s o n ,   n o   au x i liar y   p o in t  h a s   b ee n   s elec ted   b et w ee n   p o in t s   M1   an d   M2 .   No w   t h e  q u es tio n   i s   h o w   to   s elec t  th e  a u x i liar y   p o in t  i n   t h e  Fin d   Au x i liar y   P o in t  f u n cti o n .   As  it  i s   clea r   f r o m   p s e u d o   co d e,   th e  d esti n a tio n - s o u r ce   p o s itio n   i s   s p ec if ied   as  t h e  i n p u t  p r o b le m   b u t  t h e  p o s itio n   o f   au x i liar y   p o in t s   s till   r e m ain s   u n clea r .   T h e  n ex t  s ec tio n   ai m s   to   an s w er   th e  q u e s tio n   o f   wh er e  is   th e  o p ti m al   p o s itio n   f o r   th e  a u x iliar y   p o in t s .           Fi g u r e   2.   Dis p la y i n g   th e  a u x i li ar y   p o in t b et w ee n   t h e  t w o   p o in ts   o f   s o u r ce   an d   d esti n atio n         Fig u r e  3 .   Fin d   P ath   f u n ctio n   ta k es t h e  p o in ts   o f   s o u r ce   an d   d esti n a tio n ,   an d   f in d s   th e  n ec es s ar y   au x iliar y   p o in ts       3 . 2 .   F ind ing   a   Su it a ble A u x il ia ry   P o int   T o   s ea r ch   f o r   th e  au x iliar y   p o in t,  th er e  is   n ee d   to   li m it   th e  s ea r c h   s p ac e.   E m p ir ical l y ,   it  w a s   d is co v er ed   th at  t h e  o p ti m al  a u x iliar y   p o in t  i s   lo ca ted   b et w ee n   t h eso u r ce   a n d   d esti n atio n .   I n   Fi g u r e  4 ,   p o in t  A  is   th e  s o u r ce   an d   B   is   th e  d est in atio n .   I n   t h e  f ir s t  ass u m p t io n ,   th e  s q u ar e  R SP Q  w er e  co n s id er ed   an d   th e  th e  au x i liar y p o in t  w as   as s u m ed   i n   th i s   r ec tan g le.   T h e  le n g t h   o f   R Q  a n d   SP   is   h al f   o f   A B   a n d   is   p er p en d icu lar   to   A B .   A s   s ee n   i n   t h e  p r ev io u s   s ec tio n ,   th e  d i s co v er y   o f   th e  c o o r d in ates  o f   th e  a u x iliar y   p o in t  w h ich   ca n   b r ea k   th e  d ir ec t  lin e  i n to   t w o   n e w   l i n es,  an d   ca u s e  t h e  lar g e s t  d ec lin e  i n   th e  v al u e  o f   t h e  co s t  f u n ctio n   w as  ai m ed   at.   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 ,  Feb r u ar y   201 7   :  3 9 2   –   401   396   T h is   s ec tio n   tr ies  to   d ea l  w it h   h o w   to   s ea r ch   f o r   th e  a u x il ia r y   p o in t  M  i n   t h e  R SP Q  r ec tan g le.   T o   d o   th is ,   v ar io u s   m et h o d s   ar e  u s ed .     3 . 2 . 1 .   F ull   Sea rc h M et ho d   I n   t h e  Fu ll   s ea r c h   m et h o d ,   all   p o s s ib le  ca s es  ar e   ex a m i n ed .   T o   f in d   t h e  a u x iliar y   p o in t,   t h e  p o in t s   in s id e  t h e  r ec tan g le  ar e  s ea r ch ed   to   f in d   th e  b est a u x i li ar y   p o in t.   I n   th is   w a y ,   th r o u g h   ex a m i n i n g   all  th e  p o in t s   in s id e  th e  r ec tan g le  an d   t h eir   OP T   ca lcu latio n ,   t h e   p o in t M   is   s elec ted   o n   t h e  b asi s   o f   m a x i m ized   OP T .   T h is   w il l b est h elp   in   t h e  d is co v er y   o f   th e  au x iliar y   p o in t,   b u t th e  co m p u tatio n al  co s t is  v er y   h i g h .     3 . 2 . 2 .   Usi ng   P SO   T o   allev iate  th is   p r o b le m ,   P SO  [ 1 6 ]   m et h o d   ca n   b e  u s ed .   T h is   m et h o d   co n s i s ts   o f   a  s et  o f   p ar ticles,   w it h   ea ch   o n e  lo o k i n g   f o r   an   o p tim a l  s o lu tio n .   I n itiall y ,   ea ch   o f   th e  p ar ticles  ch o o s es  an   an s w er   r an d o m l y .   T h en ,   b y   c h ec k i n g   t h e  a n s w er s   an d   co n s u lti n g   t h e  p ar ticles,   th e y   m o v e  to   th e  b etter   a n s wer .   Usi n g   e v er y   b it   o f   its   o w n   e x p er ien ce   a n d   th e  b est ex p er ien ce   o f   all  t h e  p ar ti cles,  p ar ticles ca n   m o v e  b etter .           Fig u r e  4 .   T h e  p o in ts   A   an d   B   ar e  s o u r ce   an d   d esti n atio n   p o in ts .   Sear c h   s p ac e  r ec tan g le  li m it s   th e  a u x iliar y   p o in ts .   T h e  len g t h   o f   r ec ta n g le   eq u als th e  d is tan ce   o f   th e  s o u r ce   an d   d esti n atio n   a n d   th e  w i d th   o f   th e  r ec tan g le  i s   h al f   o f   i t       T h e  p o s itio n   o f   t h e  s u g g este d   au x iliar y   p o in t   in   t h e  t w o - d i m en s io n al   s p ac e  is   co n s id e r ed   as   t h e   an s w er   s p ec if icatio n s   o f   ea c h   p ar ticle  an d   t h e  p o in ts   in s id e  t h e  R SP Q  r ec ta n g le   as   th e   s ea r ch   s p ac e.   A   b etter   p o s itio n   is   o n e  w h ic h   b etter   s atis f ies  r o u tin g   co n s tr ai n ts .   So m e  p o in t s   b ec o m e  ca n d id ates  in   t h e  s ea r ch   s p ac e  r an d o m l y .   T h e n ,   t h r o u g h   P S O  p o s itio n ,   t h ese   p o in ts   ar e  o p ti m ized   to   b e  ab le  to   f i n d   th e  o p ti m al  a u x iliar y   p o in t.  I f   an   au x il iar y   p o in t c o u ld   n o t b e  f o u n d   af ter   s ev er al  r e p etitio n s ,   t h e  s ea r ch   w i ll b e  s t o p p ed .     3 . 3 .   T he  Use o f   P er pend icula r   E m p ir icall y ,   it  w as  d is co v er ed   th at  th e  o p tim a l  au x iliar y   p o in t  is   m o s tl y   ar o u n d   o r   o n   th e  p er p en d icu lar   lin e   co n n ec ti n g   th e  s o u r ce   a n d   d esti n atio n .   T h er ef o r e,   w e   ass u m ed   t h at  t h e  a u x i liar y   p o in t i s   o n   th e  p er p en d ic u lar   li n e  o f   A B .   T h is   a s s u m p tio n   co u ld   o n l y   lo o k   o n   a   p er p en d icu lar   li n e  t o   f i n d   a n   a u x il iar y   p o in t.  T h e  len g th   o f   t h e  p er p e n d icu lar   is   li m ited   to   h al f   o f   A B   s u c h   as  R S  an d   P Q.   B y   s o   d o in g ,   th e  ch ec k in g   p o in ts   ar e  g r ea tl y   r ed u ce d .       4.   T H E   R E SU L T S O F   SI M UL AT I O N   I n   th i s   s ec t io n ,   t h e  r esu lts   o f   p r ef o r m i n g   t h e  p r o p o s ed   alg o r ith m   ar e  p r esen ted   i n   a  r ea l  en v ir o n m en t.   T h e  co n s id er ed   en v ir o n m e n t  i n   t h e  p r o b lem   is   t h e  r ea l  e n v i r o n m e n t  i n   E lb u r z  Mo u n tai n s .   T h e  d im e n s io n   o f   th e  en v ir o n m e n t  i s   1 8 ,   0 0 0   b y   4 5 ,   0 0 0 ,   w it h   t h e  ac cu r ac y   o f   9 0   s q u ar e  m eter s .   A s   p r ese n t ed   in   [ 1 4 ]   th e  f u zz y   m ap   is   a  m atr i x   o f   2 0 0   b y   5 0 0 .   E ac h   p o in t  i n   t h e  m a tr ix   p r es en ted a  d ef i n ite  p er f o r m an ce   f u n ct io n s   ac co r d in g   to   th e  th r ee   s p ec i f ied   co n s tr ai n ts .   T h e  o f ier ed   alg o r ith m   w as  i m p le m en ted   o n   M A T L A B   s o f t w ar e.   I n   ea ch   ex p er i m en t,  th e  s o u r ce   an d   d esti n atio n   w er e  m ad e  clea r   b y   th e  u s er   a n d   t h e  o f ier ed   a lg o r ith m   a n n o u n ce d   t h e  te s t  r esu lt s   as  a n   o u tp u t   ac co r d in g   to   th e  p er f o r m a n ce   f u n ctio n .     Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2088 - 8708     O ff in e/On lin e  Op timu m  R o u tin g   o f a   UA V   Usi n g   A u xilia r y  P o in ts   ( A b b a s   F a d a vi )   397   4 . 1 .   Det er m i nin g   t he  Ro ute   by   A ux ilia ry   P o ints   Fig u r e  5   an d   Fig u r e  6   s h o w ,   t h e  r o u tes  o f   a  U A V  i n   t w o   d i f ier en t  e n v ir o n m en t s   an d   d if ie r en t   f u zz y   m ap s .   T h e  r o u tes  h a v e  b ee n   i d en tifie d   b y   a u x iliar y   p o in ts   ac co r d in g   to   th e  m eth o d   d esc r ib ed   in   3 . 2 .   T h ese   au x i liar y   p o i n ts   w er e  d eter m i n ed   b y   t h e  F u ll   s ea r ch   m e th o d .   B o th   f i g u r es  r elate d   to   f u zz y   m ap   ar e  m en t io n ed   an d   h av e  d i f ier en t r o u tes.   As  o b s er v ed   f r o m   Fi g u r e  5   a n d   Fi g u r e  6 ,   t h e  r o u te  o f   m o v e m e n t  w as  d eter m in ed   b y   t h e  au x iliar y   p o in t.  T h is   i m p lies   t h at  t h e  s tr aig h t lin e  b et w ee n   t h e  s o u r ce   an d   d esti n at io n   is   b r o k e n   b y   a u x i liar y   p o in t s .           Fig u r e  5 .   T h e  au x iliar y   p o in ts   d eter m in ed   b y   t h e  F u ll se ar c h   m et h o d th e  b lack   p o in t s   ar e  s o u r ce   an d   d esti n atio n   an d   t h e  r ed   p o in ts   t h e  au x iliar y   p o in ts           Fig u r e  6 .   T h e  au x iliar y   p o in ts   d eter m in ed   b y   t h e  F u ll sear c h   m et h o d th e  b lack   p o in t s   ar e  s o u r ce   an d   d esti n atio n   an d   t h e  r ed   p o in ts   th e  au x iliar y   p o in ts       T o   ex a m i n e  th e  o p ti m iza tio n   a m o u n t  b y   au x il iar y   p o in ts ,   t h e  f o llo w i n g   r elatio n   is   ex p r e s s ed   as  th e   m o s t c o m p lete  o n e:                                                                                                        ( 1 )     n   is   th e  n u m b er   o f   s e g m en t s   i n to   w h ich   th e  l in e  A B   i s   d iv i d ed .   Fo r   f u r th er   e x a m in at io n ,   1 0 0   p air s   o f   s o u r ce   an d   d esti n a tio n   p o in t s   w er e  c o n s id er ed   r an d o m l y   an d   t h e  a m o u n t  o f   av er a g e  OP T   is   r ep o r ted   in   th e  eq u atio n   ( 1 ) .   T h is   n u m b er   in d icate d   th e   p o s itiv e  ef f ec t o f   u s in g   t h e  au x iliar y   p o i n ts   i n   d eter m i n i n g   t h e  s u itab le  r o u te.     4 . 2 .   Det er m i nin g   t he  Au x ilia ry   P o ints  by   P SO   T h e  test   f o r   th e  s a m e  s o u r ce ,   d esti n atio n   an d   en v ir o n m e n ts   o f   th e  p r ev io u s   p ar t  w as  r ep ea ted .   T h e   d if f er e n ce   w a s   th e  i n   th e  d et er m in a tio n   o f   th e  a u x iliar y   p o in t  b y   P SO.  T h e  au x iliar y   p o in t  o b tain ed   f r o m   s ea r ch i n g   all  t h e  p o in ts   w as  t h e  b est  a v ailab le   au x iliar y   p o in t.  Ho w e v er ,   t h e  au x il iar y   p o in t  o b tain ed   f r o m   P SO  w a s   o n e  o f   t h e  b est   av a ilab le  au x iliar y   p o in t s .   Fo r   t h is   r ea s o n ,   t h e  o b tain ed   OP T   o f   F u ll   s ea r ch   w a s   d if f er e n t f r o m   th e  OP T   o b tain ed   f r o m   P SO.   T h e  n u m b er   o f   p ar ticles  w a s   s et  as  1 0 .   T h e  ex p er i m e n t  w a s   r ep ea ted   1 0 0   tim es.  T h e  m ea n   v a lu e   o b tain ed   b y   t h e  au x il iar y   p o in t  w it h   P SO  w as  p r esen ted   in   tab le  1 .   A s   it  is   clea r ,   t h is   a m o u n t  w as  le s s   t h a n   th e  F u ll sear c h   OP T .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 ,  Feb r u ar y   201 7   :  3 9 2   –   401   398   On e  o f   t h e  m a in   f ac to r s   i n   th e   s ea r ch   alg o r it h m   is   t h e  s ea r ch   ti m e.   I n   o r d er   to   p er f o r m   th e  alg o r ith m   o n lin e,   t h e  s ea r c h   ti m e  s h o u ld   b e  r ed u ce d   as  m in i m u m   as  p o s s ib le.   I n   t h is   ar ticle  t h e  a v er ag e  s ea r ch   ti m e  f o r   f i n d in g   t h e  r o u tes  ar e  p r esen t ed   f o r   d if f er en t  s ea r ch in g   m e th o d s .   Fo r   b et ter   co m p ar is o n   av er ag e  s ea r c h i n g   ti m e  o f   th e  t h e  a u x i liar y   p o in t   m et h o d   w it h   f u ll  s ea r ch   in   t h e  r ec tan g le  w a s   co n s id er ed   as  r ef er en ce   an d   o t h er   m et h o d   ar e  co m p ar ed   w it h   t h i s   r ef er e n ce .   T ab le  1   s h o w s   t h at  s ea r ch   ti m e  w i th   P SO  i n   t h e  s a m e  r ec ta n g le   is   o n l y   0 . 0 6   o f   th e  f u ll  s ea r ch   m e th o d .     4 . 3 .   Det er m i nin g   t he  Au x ilia ry   P o ints  o n t he  P er pend icu la r   T h e  ex p er im e n t  w a s   r ep ea ted   f o r   th e  s a m e  s o u r ce   a n d   d est in atio n   a n d   th e  p r ev io u s   e n v i r o n m e n ts ,   w it h   th e   ex ce p tio n   t h at  t h e  a u x i liar y   p o in t  o n   t h e  p er p en d icu lar   li n e  co n n ec t in g   t h e  s o u r ce   an d   d esti n atio n   w a s   d eter m in ed .   OP T   v alu e   o b tain ed   w it h   t h e  a u x iliar y   p o in ts   o n   t h e  p er p en d ic u lar   li n e  i s   s h o w n   i n   tab le  1 .   As it is cle ar ,   th is   v a lu e  w a s   le s s   t h an   F u ll  s ea r ch   OP T .   Sear c h   ti m e  d u r atio n   i s   s h o w n   i n   ta b le  1.     4 . 4 .   A  Co m pa ri s o n o f   t he  T hree   M e t ho ds   o f   Sea rc hin g   Aux ili a ry   P o ints   T h r ee   m et h o d s   in   an   e n v ir o n m en t  w it h   th e  s p ec i f ied   s o u r c e  an d   d esti n atio n   w a s   p er f o r m ed ,   an d   th e  r esu lt s   s h o w n   w i th   d i f f er en t  c o lo r s   in   Fi g u r e  7 .   A s   i t  is   cle ar   f r o m   Fi g u r e  7 ,   all  th r ee   m eth o d s   r ea ch ed   t h e   an s w er ,   b u t e ac h   w it h   d if f er en t r o u tes.           Fig u r e  7 .   R o u tes r u n n i n g   t h e  F u ll sear c h ,   P SO,  an d   th e  p er p en d icu lar   m et h o d s   ar e  s h o w n   b y   th e  co lo r s   r ed ,  g r ee n   a n d   b lack ,   r esp ec tiv el y       4 . 5 .   T he  P ro ba bil it y   o f   t he  O pti m a l  A ux i lia ry   P o int  being   Aro un d  t he  P er p endic ula r  L i ne  Co nn ec t ing   So urce   a nd   Dest ina t io n   Fig u r e  8   illu s tr ates  t h e  r atio   o f   th e  d is tan ce   to   t h e  p er p en d icu lar   lin e  to   t h e  d is ta n ce   b et w ee n   t h e   s o u r ce   an d   d es tin a tio n   i n   ter m s   o f   p er ce n ta g e.   E ac h   b ar   o f   t h e  f i g u r e  r ep r esen ts   t h e  te n   p er ce n t  to tal  o f   th e   v alu e s .   Fo r   ex a m p le;  t h e  t h ir d   b ar   r ep r esen ts   th e  n u m b er   o f   p o in ts   w h o s e  p er ce n ta g e  is   b et w ee n   2 0   an d   2 9 .   As  it  i s   clea r   f r o m   Fi g u r e  8 ,   th e  co n ce n tr atio n   o f   o p ti m al   a u x i liar y   p o in t  is   m o r e  ar o u n d   th e  p er p en d icu lar .   T h e  v alu e  o f   ze r o   f o r   th e  p o in ts   m ea n s   t h at  th e y   ar e  o n   th e  p er p en d icu lar . I n   o r d er   t o   ex a m i n e  f e w er   p o in t s ,   th e  p o in ts   o n   th e  p er p en d icu la r   in s tead   o f   t h ep o in t a r o u n d   it  ar e  co n s id er ed .           Fig u r e  8 .   th e  r atio   o f   th e  d is ta n ce   to   th e  p er p en d icu lar   li n e  t o   th e  d is tan ce   b et w ee n   th e  s o u r ce   an d   d esti n atio n   in   p er ce n t   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2088 - 8708     O ff in e/On lin e  Op timu m  R o u tin g   o f a   UA V   Usi n g   A u xilia r y  P o in ts   ( A b b a s   F a d a vi )   399   4 . 6 .   A  Co m pa riso n  w it h o t her  M et ho ds   T h e  p r o p o s ed   m eth o d   w as  co m p ar ed   w it h   t h e  t w o   m et h o d s   o f   P SO  [ 8 ]   an d   GA   [ 1 4 ] .   Fo r   t h is   r ea s o n   all  th e   t h r ee   m e th o d s   w er e  r u n   a  h u n d r ed   ti m es  i n   d i f f er en t  e n v ir o n m en t s   a n d   w it h   d i f f er en t  s o u r ce s   an d   d esti n atio n s .   I n   th is   p ap er ,   th e  o f f er ed   m eth o d   ti m e  w a s   c o n s id er ed   as  t h e  r ef er e n ce   v al u e  it  w a s   co m p ar ed   w it h   t h e  ti m e s   o b tain ed   f r o m   o th e r   m et h o d s . T ab . 1 s h o w s   th e  av er ag e  o f   th e  o b tain ed   r es u lts .   T o   im p le m en t  P SO  th e  s a m e  s etti n g s   as  s p ec if ied   in   r ef er e n ce   [ 8 ]   w er e  u s e d .   I n   s o m e  i m p le m e n tatio n s   P SO  is   ca u g h t  i n   th e   lo ca l  m i n i m u m   an d   v i s u al l y   s p ec if ied   as  f ail in g   to   r ea c h   a  s atis f ac to r y   s o lu t io n .   Fu r t h er   i m p le m en ta tio n   o f   P SO in   th i s   ca s e  d o es  n o t  h av e  a  g o o d   r es u lt.  T o   allev iate   th e  p r o b lem ,   t h e  n u m b er   o f   p ar ti cles  w a s   i n cr ea s ed .   T h e  p r o b lem   w a s   s o lv ed   b u t   th e  co m p u ta tio n al  ti m e  i n cr ea s ed .   A   r ed u ctio n   in   t h e  ti m e  ca lcu latio n s   b y   r ed u cin g   th e   n u m b er   o f   p ar ticles  w o u ld   r es u lt  i n   i n cr ea s i n g   th e  r i s k   o f   f alli n g   in to   th e  lo ca l  m i n i m u m .   C o n s eq u en tl y ,   t h e  s a m e  n u m b er   o f   r ef er en ce   p ar ticles [ 8 ]   w as u s ed .   T o   im p le m e n t  t h e  G A ,   s i m i lar   s p ec if ied   s ett in g s   i n   r e f er en ce   [ 1 4 ]   w as  ap p lied .   I t  is   n o te wo r th y   h e r e   in   G A   m et h o d ,   af ter   co m p leti o n   o f   th e  m i n i m u m   r o u ti n g ,   t h e  p ath   w a s   b ad l y   b r o k en   a n d   co m p r is ed   b r o k e n   p ar ts   w h ic h   ca n   b e  s o f te n ed   b y   th e  s o f te n er   s p ec if ied   in   r ef e r en ce   [ 1 4 ].       T ab le  1 .   R esu lts   o f   ca lcu lat in g   th e  av er a g e  p er f o r m an ce   a n d   s ea r ch   ti m e  o f   d if f er e n t  m e th o d s   in   h u n d r ed   ti m e s   o f   p ath   s ea r c h   M e t h o d   O P T   T i me   P S O [ 8 ]   1 0 . 9   2 . 3   G A [ 1 4 ]   1 2 . 1   0 . 7   T h e   u se   o f   a u x i l i a r y   p o i n t   u s i n g   t h e   F u l l   se a r c h   1 2 . 8   1   T h e   u se   o f   a u x i l i a r y   p o i n t   u s i n g   P S O   1 0 . 2   0 . 0 6   T h e   u se   o f   a u x i l i a r y   p o i n t   u s i n g   t h e   p e r p e n d i c u l a r   8 . 3   0 . 0 2 3       4 . 7 .   T he  E x a m i na t io n  o f   t he  Ra t i o   o f   t he  O P T   t o   t he  Ro ute   Vi s ua lly   I n   o r d er   to   o b tain   a  clea r   p i ctu r e  o f   th e   OP T ,   th e  f o llo win g   ex p er i m en t  w a s   co n d u c te d .   I n   th i s   ex p er i m e n t,  h u m a n   i n tel lig e n ce   w as  u s ed   to   ex a m i n e  t h e   q u alit y   o f   t h e  r o u te. A   to tal   o f   2 5   r o u te s   w er e   s elec ted   w ith   t h e  e n v ir o n m e n t  an d   s o u r ce   an d   d esti n a tio n ,   w it h o u t  h av i n g   to   co n s id e r   h o w   a  r o u te  w a s   cr ea ted .   T h e  r o u tes  w it h   th e  a m o u n t  lo w er   th a n   t w o   w er e  n o t  ex a m i n ed   b ec au s e  th e y   w e r e  n o ticea b l y   f al s e   an d   co n tai n ed   a w s .   T h ese  d ir ec tio n s   w er e  p r esen ted   to   th r ee   s k il led   u s er s   w h o   w er e  r eq u ir ed   to   v o te  f o r   an y   o f   t h e  r o u te s .   Vo te s   w er e   eit h e r   T er r i b le  ( 0 ) ,   B ad   ( 1 ) ,   m o d er ate  ( 2 ) ,   g o o d   ( 3 )   Ver y   Go o d   ( 4 ) .   Af ter   v o tin g ,   th e   av er ag e  s co r es  w er e  o b tai n ed   an d   co m p ar ed   w it h   t h e  a v er ag e  OP T   r o u tes.  Fig u r e  9   s h o w s   th e   r atio   b et w ee n   th e  OP T   an d   v o ted   p r iv ileg es.   B ec au s e  it  is   r ar e  f o r   th e  OPT  r o u te  to   b e  h ig h er   th a n   1 4 ,   th e y   w er e  av o id ed   in   th e  g r ap h .   A s   i t  is   clea r   f r o m   Fig u r e  9 ,   th e  r o u tes  w it h   OP T s   lo w er   th a n   4   w er e  s p ec i f ied   as  ter r ib le  an d   b ad ,   w h ile  th o s e   h i g h er   t h an   8   w er e  g o o d   o r   v er y   g o o d .   An o th er   is s u e  i n d icate d   t h at  t h e  h i g h e r   th e  OP T   f r o m   t h e   s p ec if ied   v al u e s ;  th e  m o r e  th e   r o u te  q u alit y   w as  b eliev ed   to   b e  s atu r ated   ac co r d in g   to   th e   v ie w er s .   Fi g u r e  7  co n f ir m ed   th i s   is s u e.   T h r ee   p ath s   h av e  u s ed   th r ee   d if f er en t   m eth o d s   b u t  n o   m u c h   d if f er e n ce   ex i s ts   b et w ee n   th eir   o b s er v ed   q u alitie s .           Fig u r e  9 . T h e  r atio   o f   th e  d is ta n ce   to   th e  p er p en d icu lar   li n e  t o   th e  d is tan ce   b et w ee n   th e  s o u r ce   an d   d esti n atio n   in   p er ce n t   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 ,  Feb r u ar y   201 7   :  3 9 2   –   401   400   5.   CO NCLU SI O N   I n   t h is   p ap er   a  ce r tain   m et h o d   w as  i n tr o d u ce d   to   f i n d   a  r o u t e  f o r   U A V   b ased   o n   s ea r ch i n g   a u x i liar y   p o in ts   i n   a  r ec ta n g le   w it h   asp ec t  r atio   o f   2 :1 .   Mo r eo v er   w e   s h o w ed   t h at  s elec ti n g   th e  a u x iliar y   p o in t  o n   t h e   p er p en d icu lar   d r am a ticall y   d ec r ea s es  th e  co m p u ta tio n al  co m p lex i t y   w h ile   th e  r o u te  is   s ti ll  d esira b le.   T h e  t w o   p ar am eter s   o f   OP T   an d   s p ee d   w er e  u s ed   to   co m p ar e  d if f er e n t  m e th o d s   w it h   ea c h   o th er .   I t  w as  f o u n d   th a t  th e   a m o u n t  o f   OP T   f o r   th e  P SO  s ea r ch   o f   a u x iliar y   p o in t  i n   t h e  r ec tan g le  p r o p o s ed   m et h o d   p o s s ess ed   th e  b est   r esu lt  co m p ar ed   w it h   t h e  o th er   m eth o d s .   T h e  p r o p o s ed   m eth o d   u s i n g   th e  p er p en d ic u lar   p o s s ess ed   th e  b es t  s p ee d   w it h   d esira b le  OPT .   I n   f ac t,  in   t h e  latter   m et h o d   a  litt le  ac cu r ac y   is   s ac r i f iced   f o r   a  lo t  o f   s p ee d   ac ce ler atio n .   T h e  au th o r s   b eliev e  th at  i f   th e  ca lcu latio n s   ar e  g o in g   to   b e  p er f o r m ed   o f f li n e  th e n   f i n d in g   th e   au x i liar y   p o in t  w it h   f u ll  s ea r ch   i n   th e   r ec tan g le   is   b etter .   H o w e v er ,   th e   s ea r c h   o n   t h e  p er p en d icu lar   i s   b etter   f o r   o n lin e  ca lc u latio n s .       RE F E R E NC E S   [1 ]   S . A .   G a u ta m ,   N.  V e rm a ,   " P a th   p l a n n in g   f o r  u n m a n n e d   a e rial  v e h i c le  b a se d   o n   g e n e ti c   a lg o rit h m   &   a rti f icia l  n e u ra l  n e tw o rk   in   3 D " ,   2 0 1 4   I n ter n a ti o n a l  C o n fer e n c e   o n   Da t a   M in i n g   a n d   In tell ig e n t  Co mp u ti n g   ( ICDM IC),   p p .   1 - 5 ,  2 0 1 4 .   [2 ]   G a o   Y a n h u i  a n d   X iao   Qia n g u i  a n d   Hu   S h o u so n g   a n d   Ju   X iao ,   " F li g h t  Co n tro l  S y ste m   S i m u latio n   P latf o rm   f o r  UA V   Ba se d   o n   In teg ra ti n g   S im u li n k   W it h   S tate f lo w" ,  T EL KOM NIKA  In d o n e sia n   J o u r n a l   o f  El e c trica l   En g i n e e rin g ,  v o l.   10 ,   p p .   9 8 5 - 9 9 1 ,   2 0 1 2 .   [3 ]   A li   M o lt a jae i  F a rid ,  " UA V   Co n tro ll e r  Ba se d   o n   A d a p ti v e   Ne u ro F u z z y   In f e re n c e   S y ste m   a n d   P I D" ,  IAE S   In ter n a t io n a l  J o u rn a l  o f  R o b o ti c s   a n d   A u to m a ti o n   ( IJ RA ) ,   v o l.   2 ,   p p .   73 - 82 ,   2 0 1 3 .   [4 ]   S . S .   Ja n ,   Y. H.  L in ,   " In teg ra ted   F l ig h t  P a t h   P la n n i n g   S y ste m   a n d   F li g h t  Co n tro l  S y ste m   f o r  Un m a n n e d   He li c o p ters " ,   S e n so rs ,  v o l .   1 1 ,   p p .   7 5 0 2 - 7 5 2 9 ,   2 0 1 1 .   [5 ]   P . P .   W u ,   D.  Ca m p b e ll ,   T .   M e r z , " M u lt i - o b jec ti v e   f o u r - d im e n sio n a l  v e h icle   m o ti o n   p lan n in g   i n   larg e   d y n a m ic   e n v iro n m e n ts " ,  S y ste ms ,   M a n ,   a n d   Cy b e rn e ti c s,  Pa rt  B:  Cy b e rn e ti c s,  IEE E  T ra n sa c ti o n s  o n ,   v o l.   41 ,   p p .   6 2 1 - 6 3 4 ,  2 0 1 1 .   [6 ]   L .   De   F il ip p is,   G .   G u g li e ri,   F .   Qu a g li o tt i, " P a th   p lan n i n g   stra teg ies   f o r  UA V S   in   3 D  e n v iro n m e n ts " ,   J o u r n a l   o f   In telli g e n t  &   Ro b o ti c   S y ste ms ,  v o l.   65 ,   p p .   2 4 7 - 2 6 4 ,  2 0 1 2 .   [7 ]   I. K.  Nik o lo s,  K . P .   V a lav a n is,   N . C.   T so u rv e lo u d is,   A . N.  Ko sta ra s ,  " Ev o lu ti o n a ry   a lg o rit h m   b a s e d   o f f li n e /o n li n e   p a th   p la n n e r  f o r  UA V   n a v ig a ti o n " ,   IEE E  T ra n sa c ti o n s o n   S y ste ms ,   M a n ,   a n d   Cy b e rn e ti c s,  Pa rt B :  C y b e rn e ti c s,  v o l.   33 ,   p p .   8 9 8 - 9 1 2 ,   2 0 0 3 .   [8 ]   J.J.  L ian g ,   H.  S o n g ,   B. Y.   Qu ,   X . B. M a o ,  " P a th   p lan n in g   b a se d   o n   d y n a m ic  m u lt i - s w a r m   p a rti c le  s w a r m   o p ti m ize r  w it h   c ro ss o v e r " ,   In telli g e n t  C o mp u ti n g   T h e o rie s a n d   Ap p li c a t io n s ,   p p .   1 5 9 - 166 ,   2 0 1 2 .   [9 ]   X iao - T in g ,   Ji  a n d   Ha i - Bi n ,   X ie  a n d   L i,   Zh o u   a n d   S h e n g - De ,   Jia ,  " F li g h t  p a t h   p lan n in g   b a se d   o n   a n   im p ro v e d   g e n e ti c   a lg o rit h m " ,   2 0 1 3   T h ir d   In ter n a ti o n a l  Co n fer e n c e   o n   In telli g e n t  S y ste m  De si g n   a n d   E n g in e e rin g   Ap p li c a ti o n s ( IS DEA) ,   p p .   7 7 5 - 7 7 8 ,  2 0 1 3 .   [1 0 ]   Y.  Ch a n g q in g ,   W .   Zh u ro n g ,  " U AV   p a t h   p lan n i n g   u sin g   G S O - DE  a lg o rit h m " ,   T ENCON 2 0 1 3 - 2 0 1 3   I EE E  Reg i o n   1 0   Co n fer e n c e   ( 3 1 1 9 4 ) ,   p p .   1 - 4 ,   2 0 1 3 .   [1 1 ]   Y.  Qu ,   Y.  Zh a n g ,   Y.   Zh a n g ,  " Op ti m a l  f li g h t  p a th   p lan n i n g   f o r  U A V s  in   3 - D  th re a t  e n v ir o n m e n t " ,   2 0 1 4   In ter n a t io n a l  C o n fer e n c e   o n   U n ma n n e d   Ai rc ra ft   S y ste ms   ( ICUAS ),   p p .   1 4 9 - 155 ,   2 0 1 4 .   [1 2 ]   V .   R o b e rg e ,   M .   T a rb o u c h i,   G .   La b o n t e ,  " Co m p a riso n   o f   p a ra ll e l  g e n e ti c   a lg o rit h m   a n d   p a rti c le  s w a r m   o p ti m iza ti o n   f o r  re a l - ti m e   U A V   p a th   p lan n in g " ,   IEE E  T ra n s a c ti o n s o n   I n d u stria l   In fo rm a ti c s,   v o l.   9 ,   p p .   1 3 2 - 1 4 1 ,   2 0 1 3 .   [1 3 ]   J.  Ko k ,   L . F .   G o n z a lez ,   N.  Ke lso n ,  " F P G A   i m p le m e n tatio n   o f   a n   e v o lu ti o n a ry   a lg o rit h m   f o r  a u to n o m o u s  u n m a n n e d   a e rial  v e h icle   o n - b o a r d   p a t h   p la n n i n g " ,   IEE E  T ra n sa c ti o n s  o n   E v o lu ti o n a ry   Co mp u ta ti o n ,   v o l .   1 7 ,   p p .   2 7 2 - 2 8 1 ,  2 0 1 3 .   [1 4 ]   P .   Ke rm a n i,   A .   Afz a li a n ,   e t  a l. ,  " F li g h t  p a th   p lan n in g   u sin g   G A   a n d   f u z z y   lo g ic  c o n sid e rin g   c o m m u n ica ti o n   c o n stra in ts , "   2 0 1 4   7 th   In ter n a ti o n a l  S y mp o siu m  o n   T e lec o mm u n ica ti o n s ( IS T ),   p p .   6 - 11 ,   2 0 1 4 .   [1 5 ]   S.  Ru ss e ll ,   P .   N o rv ig ,   A .   In telli g e n c e ,  " A  m o d e rn   a p p r o a c h " ,   Arti fi c ia l  In telli g e n c e .   Pre n ti c e - Ha ll ,   E g n lew o o d   Cli ff s ,  v o l.   2 5 ,   p p .   6 5 - 7 1 ,   1 9 9 5 .   [1 6 ]   Y.  S h i ,  " P a rti c le sw a r m   o p ti m iza t io n , "   IEE E  Co n n e c ti o n s ,  v o l.   2 ,   p p .   8 - 13 ,   2 0 0 4 .                           Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2088 - 8708     O ff in e/On lin e  Op timu m  R o u tin g   o f a   UA V   Usi n g   A u xilia r y  P o in ts   ( A b b a s   F a d a vi )   401   B I O G RAP H I E S   O F   AUTH O RS       Abb a sf a d a v i   wa s  b o rn   in   S a ri ,   Ira n   in   1 9 78 .   He   re c e iv e d   th e   B. S .   d e g re e   in   e lec tro n ic   e n g in e e rin g   f ro m   A z a d   u n iv e rsity   o f   G a r m sa r ,  G a r m sa r ,   Ira n ,   in   2 0 0 5   a n d   t h e   M . S c .   d e g re e   in   M e c h a tro n ics   f ro m   S c ien c e   a n d   Re se a rc h   Br a n c h ,   Isla m ic  Az a d   Un i v e rc it y   S e m n a n ,  S e m n a n ,  Ira n   in   2 0 1 2 .   His  re se a r c h   in tere sts  in c lu d e   Im a g e   P ro c e ss in g ,   P a tt e r n   Re c o g n it io n ,   A lg o rit m   Op ti m iza ti o n ,   a n d   Ne u ra l  Ne tw o rk s.         Alia sg h a r   B e h e s h ti   S h ira z i   He   re c e iv e d   h is  P h . D. d e g re e s  in   Dig it a l  Im a g e   P ro c e ss in g   f ro m   Ok a y a m a   Un iv e r sit y ,   Ja p a n   in   1 9 9 5 .   M r   Be h e sh t i   w a s  w it h   IUST .   His  re se a rc h   in tere sts  a re   in   Im a g e   P ro c e ss in g   a n d   C o d in g a n d   S ig n a l  P ro c e ss in g ,  C o m p u ter  Ne tw o rk in g ,  Da ta Co m m u n ica ti o n   sy ste m   d e si g n ,  S a telli te.   Em a il s    E m a il :  a b e h e sh ti   (A t)   iu st.ac . ir         Ped r a m   K e r m a n i   re c e iv e d   h is  B. En g .   d e g re e   in   El e c tri c a l  En g in e e rin g   f ro m   Isla m ic   A z a d   Un iv e rsit y ,   Teh ra n   Ira n ,   in   2 0 08 ,   a n d   M . En g .   De g re e   in   Co n tro l  En g in e e rin g   f ro m   De p a rt m e n t  o f   El e c tri c a l  a n d   C o m p u ter  En g in e e rin g ,   S h a h i d   Be h e sh ti   U n iv e rsity ,  T e h ra n   Ira n ,   i n   2 0 12 .   He   is   c u rre n tl y   a   F P GA   De sin g   E n g i n e e r  a t  Re c o re   S y ste m s,  En sc h e d e   Ne th e rlan d s .   His  re se a rc h   in tere sts   a u to n o m o u s ae rial  v e h icle s ,  p a th   p lan n in g   a n d   a rti f icia l  in t e ll ig e n c e .       Evaluation Warning : The document was created with Spire.PDF for Python.