Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Performance Evaluation of Path Planning Techniques for Unmanned Aerial Vehicles: A comparative analysis of A-star algorithm and Mixed Integer Linear Programming
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Context: Unmanned Aerial Vehicles are being widely being used for various scientific and non-scientific purposes. This increases the need for effective and efficient path planning of Unmanned Aerial Vehicles.Two of the most commonly used methods are the A-star algorithm and Mixed Integer Linear Programming.Objectives: Conduct a simulation experiment to determine the performance of A-star algorithm and Mixed Integer Linear Programming for path planning of Unmanned Aerial Vehicle in a simulated environment.Further, evaluate A-star algorithm and Mixed Integer LinearProgramming based computational time and computational space to find out the efficiency. Finally, perform a comparative analysis of A star algorithm and Mixed Integer Linear Programming and analyse the results.Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of

Objectives: Conduct a simulation experiment to determine the performance of A-star algorithm and Mixed Integer Linear Programming for path planning of Unmanned Aerial Vehicle in a simulated environment.Further, evaluate A-star algorithm and Mixed Integer LinearProgramming based computational time and computational space to find out the efficiency. Finally, perform a comparative analysis of A star algorithm and Mixed Integer Linear Programming and analyse the results.Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of

Methods: To achieve the objectives, both the methods are studied extensively, and test scenarios were generated for simulation of these methods. These methods are then implemented on these test scenarios and the computational times for both the scenarios were observed.A hypothesis is proposed to analyse the results. A performance evaluation of these methods is done and they are compared for a better performance in the generated environment.

Results: It is observed that the efficiency of A-star algorithm andMILP algorithm when no obstacles are considered is 3.005 and 12.03functions per second and when obstacles are encountered is 1.56 and10.59 functions per seconds. The results are statistically tested using hypothesis testing resulting in the inference that there is a significant difference between the computation time of A-star algorithm andMILP. Performance evaluation is done, using these results and the efficiency of algorithms in the generated environment is obtained.Conclusions: The experimental results are analysed, and the

Conclusions: The experimental results are analysed, and the efficiencies of A-star algorithm and Mixed Integer Linear Programming for a particular environment is measured. The performance analysis of the algorithm provides us with a clear view as to which algorithm is better when used in a real-time scenario. It is observed that Mixed IntegerLinear Programming is significantly better than A-star algorithm.

Place, publisher, year, edition, pages
2016. , 75 p.
Keyword [en]
A-star algorithm, Mixed Integer Linear Programming, performance evaluation, MILP
National Category
Computer Science
Identifiers
URN: urn:nbn:se:bth-13541OAI: oai:DiVA.org:bth-13541DiVA: diva2:1052215
Subject / course
DV2566 Master's Thesis (120 credits) in Computer Science
Educational program
DVAXA Master of Science Programme in Computer Science
Supervisors
Examiners
Available from: 2016-12-06 Created: 2016-12-05 Last updated: 2016-12-06Bibliographically approved

Open Access in DiVA

fulltext(811 kB)119 downloads
File information
File name FULLTEXT02.pdfFile size 811 kBChecksum SHA-512
a99cbc6d13b60e8f4f2bcae86e11f693b2254031f60f4316c3dc2a6b1e4e5ed93650df3df2a3bf2736a80ca475b26b475bf9cb1744288d5a85ce4a1806767d93
Type fulltextMimetype application/pdf

By organisation
Department of Computer Science and Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 119 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 225 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf