Energy-Efficient Path Planning with Multi-Location Object Pickup for Mobile Robots on Uneven Terrain

Autonomous Mobile Robots (AMRs) operate on battery power, making energy efficiency a critical consideration particularly in outdoor environments where terrain variations affect energy consumption. While prior research has primarily focused on computing energy-efficient paths from a source to a destination, these approaches often overlook practical scenarios where a robot needs to pick up an object en route--an action that can significantly impact energy consumption due to changes in payload. This paper introduces the Object-Pickup Minimum Energy Path Problem (OMEPP), which addresses energy-efficient route planning for Autonomous Mobile Robots (AMRs) required to pick up an object from one of the many possible locations and take it to a destination. To address the OMEPP problem, we first introduce a baseline algorithm that employs the Z* algorithm, a variant of A* tailored for energy-efficient routing, to iteratively visit each pickup point. While this approach guarantees optimality, it suffers from high computational cost due to repeated search efforts at each pickup location. To mitigate this inefficiency, we propose a concurrent PCPD search that manages multiple Z* searches simultaneously across all pickup points. Central to our solution is the Payload-Constrained Path Database (PCPD), an extension of the Compressed Path Database (CPD), a state-of-the-art technique for fast shortest path computation, that incorporates payload constraints. We further demonstrate that PCPD significantly reduces branching factors during search, leading to improved overall performance. Although the concurrent PCPD search may produce slightly suboptimal solutions, extensive experiments on real-world datasets demonstrate that it achieves near-optimal performance while being one to two orders of magnitude faster than the baseline algorithm derived from existing methods.