An improved strategy for exploring a grid polygon

DOI10.1007/978-3-642-11476-2_18MaRDI QIDQ3408174zbMATH OpenOpenAlexFDO

Authors Agnieszka Kolenderska, Adrian Kosowski, Michal Malafiejski, Paweł Żyliński

Publication date 24 February 2010

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-11476-2_18

zbMATH Keywords

competitive ratioexploration problemgrid polygonmobile robotpath planning

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The simple grid polygon exploration problem
• Computing and Combinatorics
• Competitive exploration of rectilinear polygons.
• scientific article; zbMATH DE number 1809601
• Models and algorithms for online exploration and search.

Cites work

• Approximation algorithms for lawn mowing and milling
• Competitive on-line coverage of grid environments by a mobile robot
• Computing and Combinatorics
• Graph exploration by a finite automaton
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Hamilton Paths in Grid Graphs
• Hamiltonian properties of triangular grid graphs
• scientific article; zbMATH DE number 1306896 (Why is no real title available?)
• Models and algorithms for online exploration and search.
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Tree exploration with logarithmic memory
• Undirected ST-connectivity in log-space

Cited in

(15)

• Hybrid grids and the Homing robot
• The simple grid polygon exploration problem
• Fast collaborative graph exploration
• Improved exploration of unknown polygons
• Models and algorithms for online exploration and search.
• scientific article; zbMATH DE number 1809601 (Why is no real title available?)
• Improved Grid Map Layout by Point Set Matching
• An improved on-line strategy for exploring unknown polygons
• Optimality and Competitiveness of Exploring Polygons by Mobile Robots
• Worst-case optimal exploration of terrains with obstacles
• Off-line exploration of rectangular cellular environments with a rectangular obstacle
• Computing and Combinatorics
• Exploring unknown environments with obstacles
• Optimality and competitiveness of exploring polygons by mobile robots
• Tight bounds for deterministic high-dimensional grid exploration

This page was built for publication: An improved strategy for exploring a grid polygon

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