eTheses Repository

Automated planning for hydrothermal vent prospecting using AUVs

Saigol, Zeyn A. (2011)
Ph.D. thesis, University of Birmingham.

PDF (3167Kb)


This thesis presents two families of novel algorithms for automated planning under uncertainty. It focuses on the domain of searching the ocean floor for hydrothermal vents, using autonomous underwater vehicles (AUVs). This is a hard problem because the AUV's sensors cannot directly measure the range or bearing to vents, but instead detecting the plume from a vent indicates the source vent lies somewhere up-current, within a relatively large swathe of the search area. An unknown number of vents may be located anywhere in the search area, giving rise to a problem that is naturally formulated as a partially-observable Markov decision process (POMDP), but with a very large state space (of the order of 10\(^{123}\) states). This size of problem is intractable for current POMDP solvers, so instead heuristic solutions were sought. The problem is one of chemical plume tracing, which can be solved using simple reactive algorithms for a single chemical source, but the potential for multiple sources makes a more principled approach desirable for this domain. This thesis presents several novel planning methods, which all rely on an existing occupancy grid mapping algorithm to infer vent location probabilities from observations. The novel algorithms are information lookahead and expected-entropy-change planners, together with an orienteering problem (OP) correction that can be used with either planner. Information lookahead applies online POMDP methods to the problem, and was found to be effective in locating vents even with small lookahead values. The best of the entropy-based algorithms was one that attempts to maximise the expected change in entropy for all cells along a path, where the path is found using an OP solver. This expected-entropy-change algorithm was at least as effective as the information-lookahead approach, and with slightly better computational efficiency.

Type of Work:Ph.D. thesis.
Supervisor(s):Dearden, Richard W. and Wyatt, Jeremy
School/Faculty:Colleges (2008 onwards) > College of Engineering & Physical Sciences
Department:School of Computer Science
Keywords:Intelligent Robotics Lab; Online POMDP; Partially-observable Markov decision process; Path planning; Planning under uncertainty; AUV; Hydrothermal vent; Artificial Intelligence
Subjects:QA75 Electronic computers. Computer science
Institution:University of Birmingham
ID Code:1564
This unpublished thesis/dissertation is copyright of the author and/or third parties. The intellectual property rights of the author or third parties in respect of this work are as defined by The Copyright Designs and Patents Act 1988 or as modified by any successor legislation. Any use made of information contained in this thesis/dissertation must be in accordance with that legislation and must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the permission of the copyright holder.
Export Reference As : ASCII + BibTeX + Dublin Core + EndNote + HTML + METS + MODS + OpenURL Object + Reference Manager + Refer + RefWorks
Share this item :
QR Code for this page

Repository Staff Only: item control page