The robot routing problem for collecting aggregate stochastic rewards

DOI10.4230/LIPICS.CONCUR.2017.13zbMATH Open1442.68237arXiv1704.05303OpenAlexW2606115451MaRDI QIDQ5111626FDOQ5111626

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

Publication date: 27 May 2020

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.

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

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

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)

Cites Work

• The complexity of mean payoff games on graphs
• Title not available (Why is that?)
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• Depth-First Search and Linear Graph Algorithms
• The orienteering problem: a survey
• A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane
• A characterization of the minimum cycle mean in a digraph
• On the synthesis of strategies in infinite games
• Vehicle Routing with Time Windows
• Near-optimal continuous patrolling with teams of mobile information gathering agents
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• Adaptive and sequential gridding procedures for the abstraction and verification of stochastic processes
• Quantitative Temporal Simulation and Refinement Distances for Timed Systems
• Bounding Average-Energy Games
• Controller Synthesis for Reward Collecting Markov Processes in Continuous Space
• The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

Cited In (1)

• The Robot Routing Problem for Collecting Aggregate Stochastic Rewards

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)