Shortest paths without a map

DOI10.1016/0304-3975(91)90263-2zbMATH Open0733.68065OpenAlexW1992876208WikidataQ126634813 ScholiaQ126634813MaRDI QIDQ809612FDOQ809612

Authors: Mihalis Yannakakis, Christos Papadimitriou 

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90263-2

Recommendations

• On the complexity of finding paths in a two-dimensional domain I: Shortest paths
• Walking an unknown street with bounded detour
• Stochastic shortest path problems with recourse
• scientific article; zbMATH DE number 1962828
• scientific article; zbMATH DE number 1947407

zbMATH Keywords

incomplete informationobstaclesPSPACE-completelayered graphsP-hardsearching under uncertainty

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An optimal on-line algorithm for metrical task system
• An Appraisal of Some Shortest-Path Algorithms
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Games against nature
• Title not available (Why is that?)
• An algorithm for shortest-path motion in three dimensions
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (98)

• Optimal robot localization in trees
• Efficient, optimal stochastic-action selection when limited by an action budget
• A new competitive algorithm for agent searching in unknown streets
• Penalty-based algorithms for the stochastic obstacle scene problem
• Intuitionistic layered graph logic
• Online covering salesman problem
• Complexity of node coverage games
• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• The \(k\)-Canadian travelers problem with communication
• Weighted online minimum latency problem with edge uncertainty
• Metrical service systems with multiple servers
• The Steiner traveling salesman problem with online advanced edge blockages
• The \(m\)-Steiner traveling salesman problem with online edge blockages
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• On the randomized online strategies for the \(k\)-Canadian traveler problem
• Approximating the Canadian traveller problem with online randomization
• An \(\mathrm{AO}^{*}\) based exact algorithm for the Canadian traveler problem
• Online routing and searching on graphs with blocked edges
• Advice complexity of treasure hunt in geometric terrains
• Competitive analysis of randomized online strategies for the multi-agent \(k\)-Canadian traveler problem
• Complexity of planning for connected agents in a partially known environment
• Online graph exploration on trees, unicyclic graphs and cactus graphs
• An online optimization approach for post-disaster relief distribution with online blocked edges
• Title not available (Why is that?)
• Evacuating two robots from multiple unknown exits in a circle
• Efficient strategies for robot navigation in unknown environment
• Multidimensional online motion planning for a spherical robot
• Optimal path discovery problem with homogeneous knowledge
• Shortest paths with shortest detours. A biobjective routing problem
• ONLINE ROUTING IN CONVEX SUBDIVISIONS
• Agent searching in a tree and the optimality of iterative deepening
• On the approximation of shortest escape paths
• Online Strategies for Evacuating from a Convex Region in the Plane
• Canadian traveller problem with predictions
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Online Graph Exploration: New Results on Old and New Algorithms
• The reset disambiguation policy for navigating stochastic obstacle fields
• Traveling salesman problems in temporal graphs
• Tree exploration with advice
• An on-line multi-CBR agent dispatching algorithm
• Utility-based on-line exploration for repeated navigation in an embedded graph
• On-line algorithms for weighted bipartite matching and stable marriages
• Learning-based mean-payoff optimization in an unknown MDP under omega-regular constraints
• The CNN problem and other \(k\)-server variants
• LOWER BOUNDS FOR STREETS AND GENERALIZED STREETS
• Piecemeal graph exploration by a mobile robot.
• The power of a pebble: Exploring and mapping directed graphs
• The \(k\)-server problem
• Title not available (Why is that?)
• Online graph exploration: New results on old and new algorithms
• Lower bounds in on-line geometric searching
• The Steiner traveling salesman problem with online edge blockages
• The ultimate strategy to search on \(m\) rays?
• Walking streets faster
• Going home through an unknown street
• On the two-dimensional cow search problem
• A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem
• A representation theorem for minmax regret policies
• Meeting a deadline: shortest paths on stochastic directed acyclic graphs with information gathering
• A note on the \(k\)-Canadian traveller problem
• Online algorithms for searching and exploration in the plane
• The beachcombers' problem: walking and searching with mobile robots
• PH-graphs for analyzing shortest path problems with correlated traveling times
• The Canadian Traveller Problem and its competitive analysis
• On-line path planning in an unknown polygonal environment
• Parallel searching on \(m\) rays
• Searching game trees under a partial order
• Random disambiguation paths for traversing a mapped hazard field
• Competitive complexity of mobile robot on-line motion planning problems
• On the complexity of partially observed Markov decision processes
• Shortest path through random points
• Fibonacci helps to evacuate from a convex region in a grid network
• Competitive searching in polygons—Beyond generalised streets
• A simple ant colony optimizer for stochastic shortest path problems
• Discussion of ``Network routing in a dynamic environment
• Optimal on-line algorithms for walking with minimum number of turns in unknown streets
• The weighted 2-server problem
• On a simple depth-first search strategy for exploring unknown graphs
• Interactive foundations of computing
• Multiple canadians on the road: minimizing the distance competitive ratio
• The \(k\)-Canadian travelers problem with communication
• Generalized Canadian traveller problems
• Optimal obstacle placement with disambiguations
• Agent search in uniform b-ary trees: Multiple goals and unequal costs
• Competitive algorithms for the weighted server problem
• Reactive synthesis without regret
• The covering Canadian traveller problem
• Impact of topographic information on graph exploration efficiency
• Performance bounds for planning in unknown terrain
• Worst-case optimal exploration of terrains with obstacles
• Complexity of Canadian traveler problem variants
• Competitive online routing in geometric graphs
• An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths
• Treasure hunt with advice
• Title not available (Why is that?)
• Competitive exploration of rectilinear polygons
• Online matching on a line
• The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem

This page was built for publication: Shortest paths without a map

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