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

DOI10.1016/J.DAM.2015.01.004zbMATH Open1311.05103arXiv1209.3759OpenAlexW2153817623MaRDI QIDQ2345604FDOQ2345604

Authors: Syed Talha Jawaid, Stephen Smith 

Publication date: 22 May 2015

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

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.

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

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
• Minimum latency submodular cover
• Approximation Algorithms for Orienteering and Discounted-Reward TSP

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)

Cites Work

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

Cited In (2)

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

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)