A Foraging Strategy with Risk Response for Individual Robots in Adversarial Environments

Abstract

As an essential problem in robotics, foraging means that robots collect objects from a given environment and return them to a specified location. On many occasions, robots are required to perform foraging tasks in adversarial environments, such as battlefield rescue, where potential adversaries may damage robots with a certain probability. The longer an individual robot moves through adversarial environments, the higher the probability of being damaged by adversaries. The robot system can gain utility only when the robot brings carried objects back to a predetermined home station. Such a risk of being damaged makes returning home at different locations potentially relevant to the expected utility produced by the robot. Thus, the individual robot faces a dilemma when it responds to the potential risks in adversarial environments: whether to return the carried resources home or continue foraging tasks. In this article, two fundamental environment settings are discussed, homogeneous cases and heterogeneous cases. The former is analyzed as having both the optimal substructure property and the non-aftereffect property. Then, we present a dynamic programming (DP) algorithm that can find an optimal solution with polynomial time complexity. For the latter, it is proven that finding an optimal solution is \( \mathcal {NP} \) -hard. We then propose a heuristic algorithm: A division hierarchical path planning (DHPP) algorithm that is based on the idea of dividing the foraging routes generated initially into a certain number of subroutes to dilute risks. Finally, these algorithms are extensively evaluated in simulations, concluding that in adversarial environments, they can significantly improve the productivity of an individual robot before it is damaged.