Wei, Minghan2022-03-172022-03-172021-12https://hdl.handle.net/11299/226668University of Minnesota Ph.D. dissertation. 2021. Major: Computer Science. Advisor: Volkan Isler. 1 computer file (PDF); 120 pages.Autonomous mobile robots are finding increasing use in areas such as agriculture, environmental monitoring, and search. Most field robots are currently powered by batteries and therefore have limited energy budgets. As a result, these robots have to finish tasks or visit recharging stations before the batteries run out of power. Addressing these limitations by designing energy-aware robot navigation algorithms is gaining importance in order to improve the operation time, save the robot energy, and ensure task success. The research in this dissertation focuses on energy mapping and energy-aware path planning for field robots. Specifically, we identify and address two new challenges associated with energy-constrained robot planning: (1) With the energy constraint, robots may not be able to finish the mission with onboard power. The need to visit a recharging station to get recharged and then continue the mission adds to the complexity of designing planning algorithms. New algorithms with optimality or near-optimality guarantees are needed. (2) Path planning algorithms often require environment maps. However, there is a disconnect between theoretical results and real applications because of the difficulty of obtaining energy-cost maps for planning energy-optimal paths. Modeling ground robot energy consumption on rough terrains can be rather complex. Obtaining energy-cost maps in a practical setting has not been sufficiently addressed in the prior literature. Based on these challenges, we study two research problems: energy-aware coverage path planning, and energy mapping for navigation path planning to goal locations. In the energy-aware coverage planning problem, the goal is to plan paths for robots to visit every location of given environments. Prior work tends to plan a single path for the robot, assuming an unlimited energy budget. However, the energy constraint inhibits the robots to complete coverage in one iteration especially for large environments, whichcalls for designing new planning algorithms to incorporate this restriction. We focus on a geometric version where the environment is represented as a polygonal grid with a single charging station in it. Energy consumption throughout the environment is assumed to be uniform and proportional to the moving distance. The robot needs to visit the charging station before it runs out of battery. Thus multiple paths need to be planned for coverage. The optimization goal is to minimize the total number of paths and their length. We present a constant-factor (4) approximation algorithm for contour-connected environments (defined in Chapter. 2, Sec. 2.5), and the approximation rate for general environments is proportional to the number of reflex vertices. To obtain better performance in complex environments that have many reflex vertices, we also present a log(D)-approximation algorithm, where D is the environment diameter. The second part of this dissertation focuses on the energy-mapping problem for navigation. The goal of this part is to obtain a practical energy-consumption model for ground robots, as opposed to the uniform model assumed in the energy-aware coverage planning problem. With such an energy-cost map, we can plan a path between any two locations in a given environment that consumes the least amount of energy. While there is a large amount of research on offline and online path planning algorithms given an environment map (a partial map in the online case), how to build the energy-cost map efficiently for energy-optimal path planning is less addressed. We take advantage of both aerial vehicles and ground vehicles for data collection to build energy-cost maps. The aerial robots can easily cover a large field to collect terrain appearance information. The ground robots can collect the actual energy consumption data on the field. A deep neural network is then applied to learn from both measurements and to predict the energy-cost map for the entire area. We validate our methods through simulated and real experiments and demonstrate that accurate energy-cost maps are built and paths planned by our map consume less energy compared to baseline methods. Chapter. 3 and Chapter. 4 focus on environments with and without slopes, respectively. This dissertation makes progress towards tackling robot planning challenges arising from practical constraints. The focus in our work is on the energy constraint, which can help alleviate the pressure on energy resources in world development. Other constraints robots can face in the real world can come from time and motion constraints, and sensing constraints such as the field of view of the sensors. We believe our results will bring robots to execute tasks in diverse environments under these constraints.enCoverage path planningDeep learning methodsEnergy and environment-aware automationField robotsMotion and path planningThesis or Dissertation