The Difficulty of Designing a General Heuristic Agent Navigation Strategy

Sammanfattning: 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.