On the Competitive Complexity of Navigation Tasks

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Sensor Based Intelligent Robots

• Publication date

  2000-10-15

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1007/3-540-45993-6_14
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Polygon Exploration Problem

  2002cited by this paper
• Approximation algorithms for lawn mowing and milling

  2000cited by this paper
• Geometric Shortest Paths and Network Optimization

  2000cited by this paper
• Searching Rectilinear Streets Completely

  1999influential reference
• An Optimal Strategy for Searching in Unknown Streets

  1999influential reference
• Computing Vision Points in Polygons

  1999cited by this paper
• An Optimal Competitive Strategy for Walking in Streets

  1999cited by this paper
• How to Find a Point on a Line Within a Fixed Distance

  1999cited by this paper
• Position-Independent Street Searching

  1999influential reference
• Exploring Unknown Environments with Obstacles

  1999cited by this paper
• The Exact Cost of Exploring Streets with CAB

  1998influential reference
• Two-Guard Walkability of Simple Polygons

  1998cited by this paper
• Online Algorithms

  1998cited by this paper
• LR-visibility in Polygons

  1997cited by this paper
• Optimal On-line Algorithms for Walking with Minimum Number of Turns in Unknown Streets

  1997cited by this paper
• Almost optimal on-line search in unknown streets

  1997influential reference
• Lower bounds in on-line geometric searching

  1997cited by this paper
• Hamiltonian cycles in solid grid graphs

  1997cited by this paper
• Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem

  1996cited by this paper
• Polynomial time approximation schemes for Euclidean TSP and other geometric problems

  1996cited by this paper
• Walking Streets Faster

  1996influential reference
• Generalized Streets Revisited

  1996influential reference
• A New Competitive Algorithm for Agent Searching in Unknown Streets

  1996cited by this paper
• Going Home Through an Unknown Street

  1995cited by this paper
• An approximation scheme for planar graph TSP

  1995cited by this paper
• Competitive Searching in Polygons - Beyond Generalised Streets

  1995cited by this paper
• Competitive searching in a generalized street

  1994influential reference
• Motion and visibility in simple polygons

  1994influential reference
• On-line search in a simple polygon

  1994influential reference
• Searching in the Plane

  1993cited by this paper
• Walking an unknown street with bounded detour

  1991influential reference
• Watchman Routes Under Limited Visibility

  1991cited by this paper
• Amortized efficiency of list update and paging rules

  1985cited by this paper
• Hamilton Paths in Grid Graphs

  1982cited by this paper
• Calculus of Variations (L. E. Elsgolc)

  1963cited by this paper

• Simple Grid Polygon Online Exploration Revisited

  2024cites this paper
• The simple grid polygon exploration problem

  2021influential citation
• On the approximation of shortest escape paths

  2021cites this paper
• Autonomous robot navigation

  2020cites this paper
• A 2-Approximation Algorithm for the Online Tethered Coverage Problem

  2019cites this paper
• An Improved On-line Strategy for Exploring a Simple Grid Polygon

  2018cites this paper
• Online Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot

  2016cites this paper
• Algorithms for Visibility-Based Monitoring with Robot Teams

  2016cites this paper
• Optimal Online Escape Path Against a Certificate

  2016cites this paper
• 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, Reykjavik, Iceland, June 22-24, 2016

  2016cites this paper
• Visibility-based persistent monitoring with robot teams

  2015cites this paper
• Online Coverage by a Tethered Autonomous Mobile Robot in Planar Unknown Environments

  2013influential citation
• Through the Looking Glass : Off-Line Versus On-Line Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot

  2013cites this paper
• Optimizing two-sequence functionals in competitive analysis

  2012cites this paper
• Leaving an Unknown Maze Using an Error-Prone Compass

  2010cites this paper
• On the optimality of spiral search

  2010cites this paper
• Searching for an axis-parallel shoreline

  2010cites this paper
• Competitive Complexity of Mobile Robot on-Line Motion Planning Problems

  2010cites this paper
• Multidimensional Online Motion Planning for a Spherical Robot

  2009cites this paper
• Inspecting a Set of Strips Optimally

  2009cites this paper
• Optimality and competitiveness of exploring polygons by mobile robots

  2009influential citation
• Robust Navigation in an Unknown Environment With Minimal Sensing and Representation

  2009cites this paper
• Classifying the multi robot path finding problem into a quadratic competitive complexity class

  2008cites this paper
• Comparing the Power of Robots

  2008cites this paper
• Visibility-PreservingMovementforTeams—Algorithmsfor WalkingMinimalPaths.

  2007cites this paper
• A Theory for Comparing Robot Systems

  2007cites this paper
• Geometric dilation and halving distance

  2006cites this paper
• MRSAM: a quadratically competitive multi-robot online navigation algorithm

  2006cites this paper
• Online Motion Planning Algorithm for a group of Robots Obtaining a Common Goal

  2006cites this paper
• Birgit Engels 1 Tom Kamphans 2 On the Complexity of Randolph ’ s Robot Game Technical Report 005 December

  2006cites this paper
• Randolph's Robot Game is NP-complete!

  2006cites this paper
• MRSAM : A Quadratically Competitive Multi Robots Navigation Algorithm

  2006cites this paper
• Models and algorithms for online exploration and search

  2006cites this paper
• Qualitative Topological Coverage of Unknown Environments by Mobile Robots

  2006cites this paper
• Exploring Simple Grid Polygons

  2005cites this paper
• Competitive online searching for a ray in the plane

  2005cites this paper
• On optimizing multi-sequence functionals for competitive analysis

  2005cites this paper
• Optimal Competitive Online Ray Search with an Error-Prone Robot

  2005cites this paper
• CBUG: A Quadratically Competitive Mobile Robot Navigation Algorithm

  2005cites this paper
• Competitive search ratio of graphs and polygons

  2004cites this paper
• Competitive Complexity of Mobile Robot On Line Motion Planning Problems

  2004cites this paper
• CautiousBug: a competitive algorithm for sensory-based robot navigation

  2004cites this paper
• The Pledge Algorithm Reconsidered under Errors in Sensors and Motion

  2003cites this paper
• Competitive on-line coverage of grid environments by a mobile robot

  2003cites this paper
• Online Scan Coverage of Grid Environments by a Mobile Robot

  2002cites this paper
• Spiral-STC: an on-line coverage algorithm of grid environments by a mobile robot

  2002cites this paper