Change search
ReferencesLink to record
Permanent link

Direct link
The Difficulty of Designing a General Heuristic Agent Navigation Strategy
Uppsala University, Disciplinary Domain of Humanities and Social Sciences, Faculty of Social Sciences, Department of Informatics and Media, Information Systems.
Uppsala University, Disciplinary Domain of Humanities and Social Sciences, Faculty of Social Sciences, Department of Informatics and Media, Information Systems.
2011 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

We consider an abstract representation of some environment in which an agent is located. Given a goal sequence, we ask what strategy said agent - utilizing readily available algorithmic tools - should incorporate to successfully find a valid traversal route such that it is optimal in accordance with a predefined error-margin. We present four scenarios that each incorporate aspects common to general navigation to further illustrate some of the difficult problems needed to be solved in any general navigation strategy. Two reinforcement learning and four graph path planning algorithms are studied and applied on said predefined scenarios. Through the introduction of a long-term strategy model we allow comparative study of the result of the applications, and note a distinct difference in performance. Further, we discuss the lack of a probabilistic algorithmic approach and why it should be an option in any general strategy as it allows verifiably "good" estimated solutions, useful when the problem at hand is NP-hard. Several meta-level concepts are introduced and discussed to further illustrate the difficulty in producing an optimal strategy with an explicit long-term horizon. We argue for a non-deterministic approach, looking at the apparent gain of epsilon-randomness when incorporated by a reinforcement learning agent. Several problems that may arise with non-determinism are discussed, based on the notion that such an agents' performance can be viewed as a markov chain; possibly resulting in suboptimal paths concerning norm.

Place, publisher, year, edition, pages
2011. , 51 p.
Keyword [en]
Agent Navigation, Path Planning, Heuristics, Nondeterminism, Artificial Intelligence, Terrain Exploration Optimization
Identifiers
URN: urn:nbn:se:uu:diva-154690OAI: oai:DiVA.org:uu-154690DiVA: diva2:421683
Educational program
Programme in Computer Science
Uppsok
Technology
Supervisors
Available from: 2011-06-15 Created: 2011-06-09 Last updated: 2011-06-15Bibliographically approved

Open Access in DiVA

fulltext(712 kB)281 downloads
File information
File name FULLTEXT01.pdfFile size 712 kBChecksum SHA-512
4eaf3e6e46dc7dc18a1128ea2dd61ae5b3f26105973d77d7882f6d9160d8dc53e1046fbbef56afc8efb85d36d7676dd002a53061a1c771d595b9dd6189c7d8e8
Type fulltextMimetype application/pdf

By organisation
Information Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 281 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: 824 hits
ReferencesLink to record
Permanent link

Direct link