Shortest paths without a map
From MaRDI portal
Publication:809612
DOI10.1016/0304-3975(91)90263-2zbMath0733.68065MaRDI QIDQ809612
Christos H. Papadimitriou, Mihalis Yannakakis
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
incomplete information; PSPACE-complete; obstacles; layered graphs; P-hard; searching under uncertainty
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Unnamed Item, LOWER BOUNDS FOR STREETS AND GENERALIZED STREETS, ONLINE ROUTING IN CONVEX SUBDIVISIONS, Unnamed Item, A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem, Lower bounds in on-line geometric searching, The ultimate strategy to search on \(m\) rays?, Parallel searching on \(m\) rays, Efficient, optimal stochastic-action selection when limited by an action budget, Agent search in uniform b-ary trees: Multiple goals and unequal costs, On-line path planning in an unknown polygonal environment, Performance bounds for planning in unknown terrain, An on-line multi-CBR agent dispatching algorithm, Tree exploration with advice, A note on the \(k\)-Canadian traveller problem, On the two-dimensional cow search problem, Weighted nearest neighbor algorithms for the graph exploration problem on cycles, A representation theorem for minmax regret policies, The Canadian Traveller Problem and its competitive analysis, Interactive foundations of computing, Utility-based on-line exploration for repeated navigation in an embedded graph, Competitive algorithms for the weighted server problem, Agent searching in a tree and the optimality of iterative deepening, On-line algorithms for weighted bipartite matching and stable marriages, On the complexity of partially observed Markov decision processes, Optimal on-line algorithms for walking with minimum number of turns in unknown streets, Online matching on a line, Piecemeal graph exploration by a mobile robot., Optimal robot localization in trees, The power of a pebble: Exploring and mapping directed graphs, Competitive online routing in geometric graphs, The weighted 2-server problem, The CNN problem and other \(k\)-server variants, Competitive exploration of rectilinear polygons, The k-Canadian Travelers Problem with Communication, The reset disambiguation policy for navigating stochastic obstacle fields, Online Graph Exploration: New Results on Old and New Algorithms, MULTIDIMENSIONAL ONLINE MOTION PLANNING FOR A SPHERICAL ROBOT, COMPETITIVE COMPLEXITY OF MOBILE ROBOT ON-LINE MOTION PLANNING PROBLEMS
Cites Work
