Constraint-Based Coverage Path Planning: A Novel Approach to Achieving Energy-Efficient Coverage

Abstract

Despite substantial technological progress that has driven the proliferation of robots across various industries and aspects of our lives, the lack of a decisive breakthrough in electrical energy storage capabilities has restrained this trend, particularly with respect to mobile robots designed for use in unstructured and unknown field environments. The fact that these domains are often less accessible and previously unexplored makes them a perfect candidate for the use of robots, but at the same time raises the stakes of failures such as premature energy depletion, which can result in various irrecoverable scenarios leading to loss of time and equipment. If we are to successfully leverage robots for these promising applications in the absence of a revolutionary development in battery technology, it is clear we must consider alternative means of addressing the energy storage issue.

Fortunately, many of the features that contribute to the difficulty of real-world field scenarios can actually be a source of ambient energy that can be captured and exploited to extend operation beyond what is possible using limited on-board energy supply. In fact, humans have been harnessing the power of wind and currents to travel the oceans for centuries and continue to take into account ambient energy when performing various activities, either by instinct or design. The premise of this thesis is that this same thinking can be extended to planning for mobile robots in the field in order to mitigate the shortcomings of present day energy storage technology and open up further opportunities for robotic exploitation.

In particular, this thesis considers the problem of energy-efficient Coverage Path Planning (CPP) in river domains where ambient energy is present in forms such as wind, currents, or elevation change. Instead of formulating a specialized monolithic algorithm to achieve energy-efficiency in a given set of scenarios, we instead develop a novel constraint-based coverage path planning (CB-CPP) framework, which breaks down the planning process into discrete stages that can be optimized and tuned individually. This approach allows us to specifically consider the energy-use implications of the order in which different parts of the region are covered as well as the vehicle's direction of travel in each region. Finally, we propose several new energy-efficient coverage planners implemented within our CB-CPP framework that leverage these insights. We demonstrate and validate this work on a variety of simulation scenarios across domains and with real-world experiments with an autonomous surface vehicle deployed in rivers.