A sub-modular receding horizon solution for mobile multi-agent persistent monitoring. (May 2021)

• Record Type: Journal Article
• Authors: Rezazadeh, Navid; Kia, Solmaz S.
• Is Part Of: Automatica. Volume 127(2021)
• Publication Date: 2021-05
• Subjects: Persistent monitoring -- Optimal policy design -- Submodular optimization; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2020.109460
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: We consider persistent monitoring of a finite number of inter-connected geographical nodes by a group of heterogeneous mobile agents. We assign to each geographical node a concave and increasing reward function that resets to zero after an agent's visit. Then, we design the optimal dispatch policy of which nodes to visit at what time and by what agent by finding a policy set that maximizes a utility that is defined as the total reward collected at visit times. We show that this optimization problem is NP-hard and its computational complexity increases exponentially with the number of the agents and the length of the mission horizon. By showing that the utility function is a monotone increasing and submodular set function of agents' policy, we propose a suboptimal dispatch policy design with a known optimality gap. To reduce the time complexity of constructing the feasible search set and also to induce robustness to changes in the operational factors, we perform our suboptimal policy design in a receding horizon fashion. Then, to compensate for the shortsightedness of the receding horizon approach we add a new term to our utility, which provides a measure of nodal importance beyond the receding horizon. This term gives the policy design an intuition to steer the agents towards the nodes with higher rewards on the patrolling graph. Finally, we discuss how our proposed algorithm can be implemented in a decentralized manner. A simulation study demonstrates our results.