Informative path planning as a maximum traveling salesman problem with submodular rewards

DOI10.1016/J.DAM.2015.01.004MaRDI QIDQ2345604zbMATH OpenOpenAlexFDO

Authors Syed Talha Jawaid, Stephen Smith

Publication date 22 May 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.3759

zbMATH Keywords

traveling salesman problemsubmodular function maximizationinformative path planning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22)

Abstract: In this paper, we look at the problem of finding the tour of maximum reward on an undirected graph where the reward is a submodular function, that has a curvature of $kappa$, of the edges in the tour. This problem is known to be NP-hard. We analyze two simple algorithms for finding an approximate solution. Both algorithms require $O(|V{|}^3)$ oracle calls to the submodular function. The approximation factors are shown to be $frac12+kappa$ and $maxsetfrac23(2+kappa),2/3(1-kappa)$, respectively; so the second method has better bounds for low values of $kappa$. We also look at how these algorithms perform for a directed graph and investigate a method to consider edge costs in addition to rewards. The problem has direct applications in monitoring an environment using autonomous mobile sensors where the sensing reward depends on the path taken. We provide simulation results to empirically evaluate the performance of the algorithms.

Recommendations

• Submodularity and the traveling salesman problem
• A mobile multi-agent sensing problem with submodular functions under a partition matroid
• Adaptive submodular ranking and routing
• Approximation Algorithms for Orienteering and Discounted-Reward TSP

Cites work

• scientific article; zbMATH DE number 3910163 (Why is no real title available?)
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A threshold of ln n for approximating set cover
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• An analysis of approximations for maximizing submodular set functions—I
• Better approximations for max TSP
• Combinatorial optimization. Theory and algorithms.
• Cooperative forest fire surveillance using a team of small unmanned air vehicles
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• Efficient informative sensing using multiple robots
• Greedy in Approximation Algorithms
• Introduction to algorithms
• Maximizing Non-monotone Submodular Functions
• Maximizing a monotone submodular function subject to a matroid constraint
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Non-monotone submodular maximization under matroid and knapsack constraints
• Optimal value of information in graphical models
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular maximization over multiple matroids via generalized exchange properties
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The greedy travelling salesman's problem
• Worst case analysis of greedy type algorithms for independence systems

Cited in

(2)

• Spatial coverage in routing and path planning problems
• Submodularity and the traveling salesman problem

This page was built for publication: Informative path planning as a maximum traveling salesman problem with submodular rewards

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345604)