Ming Lung Raymond Chong

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-123

May 13, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-123.pdf

Path planning for mobile robots has been, and remains, a design and development challenge. In addition to well known path planning tasks such as searching for a shortest path from a start point to its end, Coverage Path Planning (CPP) is a task to design a trajectory by which agents can traverse every point in an area of interest. Generating an efficient CPP algorithm is, therefore, far more challenging than calculating a shortest path. In particular, environments with both static and dynamic obstacles require robots to navigate efficiently while simultaneously avoiding obstructions and other potential agents. Traditional approaches to address the challenges that dynamic obstacles introduce often require replanning strategies for coverage as the environment changes. Such replanning mechanisms and computations are both expensive and suboptimal, often resulting in path detours.

In this report, we first investigate several methods for conducting CPP with dynamic obstacles using a graph search algorithm (Spanning Tree Coverage) and on-policy reinforcement learning algorithm (Proximal Policy Optimization) separately. Then, we introduce a guided reinforcement learning approach for CPP which incorporates a unique reward structure as well as additional coverage information generated from Spanning Tree Coverage to help guide the reinforcement learning agent algorithm. We evaluate our proposed algorithm, Coverage Path Planning through Guided Reinforcement Learning (CPP-GRL), across different settings (grid sizes and obstacle locations) and compare with prior research methods. Experimental results show that CPP-GRL generalizes well for both stochastic and deterministic moving obstacles and performing very similarly to other control-based and learning-based algorithms, but with fewer constraints (such as following specific control laws) and lower computational power (such as using Convolutional Neural Network instead).

Advisors: Claire Tomlin

---

BibTeX citation:

@mastersthesis{Chong:EECS-2022-123,
    Author= {Chong, Ming Lung Raymond},
    Title= {Coverage Path Planning in Dynamic Environment through Guided Reinforcement Learning},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-123.html},
    Number= {UCB/EECS-2022-123},
    Abstract= {Path planning for mobile robots has been, and remains, a design and development challenge. In addition to well known path planning tasks such as searching for a shortest path from a start point to its end, Coverage Path Planning (CPP) is a task to design a trajectory by which agents can traverse every point in an area of interest. Generating an efficient CPP algorithm is, therefore, far more challenging than calculating a shortest path. In particular, environments with both static and dynamic obstacles require robots to navigate efficiently while simultaneously avoiding obstructions and other potential agents. Traditional approaches to address the challenges that dynamic obstacles introduce often require replanning strategies for coverage as the environment changes. Such replanning mechanisms and computations are both expensive and suboptimal, often resulting in path detours.

In this report, we first investigate several methods for conducting CPP with dynamic obstacles using a graph search algorithm (Spanning Tree Coverage) and on-policy reinforcement learning algorithm (Proximal Policy Optimization) separately. Then, we introduce a guided reinforcement learning approach for CPP which incorporates a unique reward structure as well as additional coverage information generated from Spanning Tree Coverage to help guide the reinforcement learning agent algorithm. We evaluate our proposed algorithm, Coverage Path Planning through Guided Reinforcement Learning (CPP-GRL), across different settings (grid sizes and obstacle locations) and compare with prior research methods. Experimental results show that CPP-GRL generalizes well for both stochastic and deterministic moving obstacles and performing very similarly to other control-based and learning-based algorithms, but with fewer constraints (such as following specific control laws) and lower computational power (such as using Convolutional Neural Network instead).},
}

EndNote citation:

%0 Thesis
%A Chong, Ming Lung Raymond 
%T Coverage Path Planning in Dynamic Environment through Guided Reinforcement Learning
%I EECS Department, University of California, Berkeley
%D 2022
%8 May 13
%@ UCB/EECS-2022-123
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-123.html
%F Chong:EECS-2022-123