Skip to main content
eScholarship
Open Access Publications from the University of California

UCLA

UCLA Electronic Theses and Dissertations bannerUCLA

An Application of Reinforcement Learning Techniques in Traditional Pathfinding

Abstract

Modern-day navigation relies on pathfinding algorithms to determine the shortest distance between two locations. These algorithms search graphs robustly, starting at an initial node and analyzing adjacent positions connecting to the destination. Even though this technique consistently finds optimal routes, pathfinding is dependent on prior knowledge of a given environment. Reinforcement learning is a branch of machine learning capable of achieving similar results through efficient exploration, data collection, and exploitation. A form of artificial intelligence, reinforcement learning focuses on understanding the environment through incentives and penalties to make optimal decisions, eventually leading to desired target convergence. This research trains three model-free reinforcement learning techniques, advantage actor-critic (A2C), proximal policy optimization (PPO), and deep Q-network (DQN) on custom maze environments. In comparison with Dijkstra’s algorithm, a standard pathfinding approach, results indicate that DQN can find analogous routes, especially when pre-trained with expert- guided behavior to reach these optimal solutions in a time-efficient manner.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View