Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh

Pathfinding is a navigation component of the agent in an Evacuation Model. Most models apply pathfinding approach to provide global information to the agent from the start due to the assumption that evacuees would always head towards the nearest exit and all exits are used equally. Realistically, ev...

Full description

Saved in:

Bibliographic Details
Main Author:	Mohd. Othman, Mohamad Nurfalihin
Format:	Thesis
Language:	English
Published:	2017
Subjects:	QA75 Electronic computers Computer science
Online Access:	http://eprints.utm.my/id/eprint/78810/1/MohamadNurfalihinMohdMFC2017.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.78810
record_format	uketd_dc
spelling	my-utm-ep.788102018-09-17T04:13:05Z Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh 2017-03 Mohd. Othman, Mohamad Nurfalihin QA75 Electronic computers. Computer science Pathfinding is a navigation component of the agent in an Evacuation Model. Most models apply pathfinding approach to provide global information to the agent from the start due to the assumption that evacuees would always head towards the nearest exit and all exits are used equally. Realistically, evacuees may only perceive its immediate surroundings, and be oblivious of other exits if the evacuee is unfamiliar with the environment. In evacuation, people tend to move towards familiar direction, which is the way they came in, and current solution of applying shortest path or least cost search approach does not demonstrate this emergent behaviour. In this study, as the counterpart of human, agents emulating human physical capabilities and limitations were developed in Unity3D Game Engine. The perception component of agent imitated human conic vision using Raycasting technique while its movement speed was limited to average movement speed of median population. Using input from Raycasting, a pathfinding algorithm based on the random mouse algorithm with localization feature using Navigation Mesh was developed. The environment for testing was built in the form of a maze in Unity3D and recordings were made to detect the agent arriving at the exit or not, and the time taken to navigate the environment in each iteration. Navigation Mesh was generated to represent walkable areas, and static obstacles that confined the spaces were labeled as walls. Unrendered cubes were placed at every intersection and exit, and were labeled accordingly. Result of the simulation showed that the pathfinding algorithm allowed the agent to successfully traverse the partially observable environment without prior knowledge, and the agent had demonstrated emergent behaviour with the integration of limited perception distance and realistic movement speed. The findings have shown that the algorithm can be used to simulate emergent behaviour in an Evacuation Model. 2017-03 Thesis http://eprints.utm.my/id/eprint/78810/ http://eprints.utm.my/id/eprint/78810/1/MohamadNurfalihinMohdMFC2017.pdf application/pdf en public http://dms.library.utm.my:8080/vital/access/manager/Repository/vital:110852 masters Universiti Teknologi Malaysia, Faculty of Computing Faculty of Computing
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA75 Electronic computers Computer science
spellingShingle	QA75 Electronic computers Computer science Mohd. Othman, Mohamad Nurfalihin Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh
description	Pathfinding is a navigation component of the agent in an Evacuation Model. Most models apply pathfinding approach to provide global information to the agent from the start due to the assumption that evacuees would always head towards the nearest exit and all exits are used equally. Realistically, evacuees may only perceive its immediate surroundings, and be oblivious of other exits if the evacuee is unfamiliar with the environment. In evacuation, people tend to move towards familiar direction, which is the way they came in, and current solution of applying shortest path or least cost search approach does not demonstrate this emergent behaviour. In this study, as the counterpart of human, agents emulating human physical capabilities and limitations were developed in Unity3D Game Engine. The perception component of agent imitated human conic vision using Raycasting technique while its movement speed was limited to average movement speed of median population. Using input from Raycasting, a pathfinding algorithm based on the random mouse algorithm with localization feature using Navigation Mesh was developed. The environment for testing was built in the form of a maze in Unity3D and recordings were made to detect the agent arriving at the exit or not, and the time taken to navigate the environment in each iteration. Navigation Mesh was generated to represent walkable areas, and static obstacles that confined the spaces were labeled as walls. Unrendered cubes were placed at every intersection and exit, and were labeled accordingly. Result of the simulation showed that the pathfinding algorithm allowed the agent to successfully traverse the partially observable environment without prior knowledge, and the agent had demonstrated emergent behaviour with the integration of limited perception distance and realistic movement speed. The findings have shown that the algorithm can be used to simulate emergent behaviour in an Evacuation Model.
format	Thesis
qualification_level	Master's degree
author	Mohd. Othman, Mohamad Nurfalihin
author_facet	Mohd. Othman, Mohamad Nurfalihin
author_sort	Mohd. Othman, Mohamad Nurfalihin
title	Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh
title_short	Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh
title_full	Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh
title_fullStr	Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh
title_full_unstemmed	Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh
title_sort	agent-based pathfinding algorithm in partially observable environment using raycasting and navigation mesh
granting_institution	Universiti Teknologi Malaysia, Faculty of Computing
granting_department	Faculty of Computing
publishDate	2017
url	http://eprints.utm.my/id/eprint/78810/1/MohamadNurfalihinMohdMFC2017.pdf
_version_	1747818076829646848

Agent-based pathfinding algorithm in partially observable environment using raycasting and navigation Mesh

Similar Items