Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding

Pathfinding is essential and necessary for agent movement used in computer games and many other applications. Generally, the pathfinding algorithm searches the feasible shortest path from start to end locations. This task is computationally expensive and consumes large memory, particularly in a larg...

Full description

Saved in:

Bibliographic Details
Main Author:	Sabri, Aimi Najwa
Format:	Thesis
Language:	English
Published:	2019
Subjects:	QA Mathematics
Online Access:	http://eprints.utm.my/id/eprint/98394/1/AimiNajwaSabriMSC2019.pdf%20%281%29.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.98394
record_format	uketd_dc
spelling	my-utm-ep.983942022-12-12T07:12:22Z Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding 2019 Sabri, Aimi Najwa QA Mathematics Pathfinding is essential and necessary for agent movement used in computer games and many other applications. Generally, the pathfinding algorithm searches the feasible shortest path from start to end locations. This task is computationally expensive and consumes large memory, particularly in a large map size. Obstacle avoidance in the game environment increases the complexity to find a new path in the search space. A huge number of algorithms, including heuristic and metaheuristics approaches, have been proposed to overcome the pathfinding problem. Artificial Bee Colony (ABC) is a metaheuristic algorithm that is robust, has fast convergence, high flexibility, and fewer control parameters. However, the best solution founded by the onlooker bee in the presence of constraints is still insufficient and not always satisfactory. A number of variant ABC algorithms have been proposed to achieve the optimal solution. However, it is difficult to simultaneously achieve the optimal solution. Alternatively, Flower Pollination Algorithm (FPA) is one of promising algorithms in optimising problems. The algorithm is easier to implement and faster to reach an optimum solution. Thus, this research proposed Artificial Bee Colony – Flower Pollination Algorithm to solve the pathfinding problem in games, in terms of path cost, computing time, and memory. The result showed that ABC-FPA improved the path cost result by 81.68% and reduced time by 97.84% as compared to the ABC algorithm, which led to a better pathfinding result. This performance indicated that ABC-FPA pathfinding gave better quality pathfinding results. 2019 Thesis http://eprints.utm.my/id/eprint/98394/ http://eprints.utm.my/id/eprint/98394/1/AimiNajwaSabriMSC2019.pdf%20%281%29.pdf application/pdf en public http://dms.library.utm.my:8080/vital/access/manager/Repository/vital:144587 masters Universiti Teknologi Malaysia Faculty of Engineering - School of Computing
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA Mathematics
spellingShingle	QA Mathematics Sabri, Aimi Najwa Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding
description	Pathfinding is essential and necessary for agent movement used in computer games and many other applications. Generally, the pathfinding algorithm searches the feasible shortest path from start to end locations. This task is computationally expensive and consumes large memory, particularly in a large map size. Obstacle avoidance in the game environment increases the complexity to find a new path in the search space. A huge number of algorithms, including heuristic and metaheuristics approaches, have been proposed to overcome the pathfinding problem. Artificial Bee Colony (ABC) is a metaheuristic algorithm that is robust, has fast convergence, high flexibility, and fewer control parameters. However, the best solution founded by the onlooker bee in the presence of constraints is still insufficient and not always satisfactory. A number of variant ABC algorithms have been proposed to achieve the optimal solution. However, it is difficult to simultaneously achieve the optimal solution. Alternatively, Flower Pollination Algorithm (FPA) is one of promising algorithms in optimising problems. The algorithm is easier to implement and faster to reach an optimum solution. Thus, this research proposed Artificial Bee Colony – Flower Pollination Algorithm to solve the pathfinding problem in games, in terms of path cost, computing time, and memory. The result showed that ABC-FPA improved the path cost result by 81.68% and reduced time by 97.84% as compared to the ABC algorithm, which led to a better pathfinding result. This performance indicated that ABC-FPA pathfinding gave better quality pathfinding results.
format	Thesis
qualification_level	Master's degree
author	Sabri, Aimi Najwa
author_facet	Sabri, Aimi Najwa
author_sort	Sabri, Aimi Najwa
title	Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding
title_short	Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding
title_full	Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding
title_fullStr	Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding
title_full_unstemmed	Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding
title_sort	hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding
granting_institution	Universiti Teknologi Malaysia
granting_department	Faculty of Engineering - School of Computing
publishDate	2019
url	http://eprints.utm.my/id/eprint/98394/1/AimiNajwaSabriMSC2019.pdf%20%281%29.pdf
_version_	1776100585326510080

Hybrid artificial bee colony and flower pollination algorithm for grid-based optimal pathfinding

Similar Items