The robot routing problem for collecting aggregate stochastic rewards

DOI10.4230/LIPICS.CONCUR.2017.13MaRDI QIDQ5111626zbMATH OpenOpenAlexFDO

Authors Rayna Dimitrova, Ivan Gavran, Rupak Majumdar, Vinayak S. Prabhu, Sadegh Esmaeil Zadeh Soudjani

Publication date 27 May 2020

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

zbMATH Keywords

discountingpath planninggraph gamesquantitative objectives

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Artificial intelligence for robotics (68T40) Games involving graphs (91A43)

Abstract: We propose a new model for formalizing reward collection problems on graphs with dynamically generated rewards which may appear and disappear based on a stochastic model. The *robot routing problem* is modeled as a graph whose nodes are stochastic processes generating potential rewards over discrete time. The rewards are generated according to the stochastic process, but at each step, an existing reward disappears with a given probability. The edges in the graph encode the (unit-distance) paths between the rewards' locations. On visiting a node, the robot collects the accumulated reward at the node at that time, but traveling between the nodes takes time. The optimization question asks to compute an optimal (or epsilon-optimal) path that maximizes the expected collected rewards. We consider the finite and infinite-horizon robot routing problems. For finite-horizon, the goal is to maximize the total expected reward, while for infinite horizon we consider limit-average objectives. We study the computational and strategy complexity of these problems, establish NP-lower bounds and show that optimal strategies require memory in general. We also provide an algorithm for computing epsilon-optimal infinite paths for arbitrary epsilon > 0.

Recommendations

• Controller synthesis for reward collecting Markov processes in continuous space
• The maximum collection problem with time-dependent rewards
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• scientific article; zbMATH DE number 7053373
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering

Cites work

• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane
• A characterization of the minimum cycle mean in a digraph
• Adaptive and sequential gridding procedures for the abstraction and verification of stochastic processes
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• Bounding Average-Energy Games
• Controller synthesis for reward collecting Markov processes in continuous space
• Depth-First Search and Linear Graph Algorithms
• Near-optimal continuous patrolling with teams of mobile information gathering agents
• On the synthesis of strategies in infinite games
• Quantitative Temporal Simulation and Refinement Distances for Timed Systems
• The complexity of mean payoff games on graphs
• The orienteering problem: a survey
• The robot routing problem for collecting aggregate stochastic rewards
• Vehicle Routing with Time Windows

Cited in

(2)

• The robot routing problem for collecting aggregate stochastic rewards
• Controller synthesis for reward collecting Markov processes in continuous space

This page was built for publication: The robot routing problem for collecting aggregate stochastic rewards

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