A sub-modular receding horizon solution for mobile multi-agent persistent monitoring
From MaRDI portal
Abstract: We study the problem of 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 proceed to 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 for reward distribution beyond the feasible policies of the agents over the receding horizon, we add a new term to our utility, which provides a measure of nodal importance beyond the receding horizon's sight. 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.
Recommendations
- Optimal control for multi-agent persistent monitoring
- Event-driven receding horizon control for distributed persistent monitoring in network systems
- Minimax persistent monitoring of a network system
- Optimal control of multi-agent persistent monitoring systems with performance constraints
- Greedy initialization for distributed persistent monitoring in network systems
Cites work
- A Supermodular Optimization Framework for Leader Selection Under Link Noise in Linear Multi-Agent Systems
- Combinatorial Algorithms for Control of Biological Regulatory Networks
- Distributed Submodular Maximization With Limited Information
- Gossip coverage control for robotic networks: dynamical systems on the space of partitions
- Graph theory with applications
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- scientific article; zbMATH DE number 1950764 (Why is no real title available?)
- scientific article; zbMATH DE number 3895002 (Why is no real title available?)
- Introduction to algorithms.
- Model predictive control: Theory and practice - a survey
- Multi-robots Gaussian estimation and coverage control: from client-server to peer-to-peer architectures
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- On Submodularity and Controllability in Complex Dynamical Networks
- Reducibility among combinatorial problems
- The minimum latency problem
Cited in
(11)- Policies for risk-aware sensor data collection by mobile agents
- Event-driven receding horizon control for distributed persistent monitoring in network systems
- Greedy initialization for distributed persistent monitoring in network systems
- A mobile multi-agent sensing problem with submodular functions under a partition matroid
- Minimax persistent monitoring of a network system
- Optimal control of multi-agent persistent monitoring systems with performance constraints
- Near-optimal continuous patrolling with teams of mobile information gathering agents
- Optimal control for multi-agent persistent monitoring
- Distributed strategy selection: a submodular set function maximization approach
- An exact solution approach for the mobile multi‐agent sensing problem
- Receding horizon control for persistent monitoring tasks with monitoring count requirements
This page was built for publication: A sub-modular receding horizon solution for mobile multi-agent persistent monitoring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664210)
