En mobil robot som representeras av en punkt som rör sig i planet måste utforska en okänd plan terräng med ogenomträngliga hinder. Både terrängen och hindren är modellerade som godtyckliga polygoner. Vi överväger två scenarier: den obegränsade sikten, när roboten ligger vid en punkt p i terrängen utforskar (se) alla punkter q i terrängen där segmentet pq tillhör terrängen, och den begränsade sikten, när vi kräver dessutom att avståndet mellan p och q är högst 1. Alla punkter i terrängen (utom hinder) måste undersökas och utförandet av en prospekteringsalgoritm, som kallas dess komplexitet, mäts efter längden på robotens bana. För obegränsad sikt visar vi en prospekteringsalgoritm med komplexitet O(P +D ε k), där P är den totala omkretsen av terrängen (inklusive omkretsen av hinder), D är diametern på den konvexa skrovet i terrängen, och k är antalet hinder. Vi antar inte kunskap om dessa parametrar. Vi visar också en matchande nedre gräns som visar att ovanstående komplexitet är optimal, även om terrängen är känd för roboten. För begränsad sikt visar vi prospekteringsalgoritmer med komplexitet O(P + A + ε Ak), där A är området i terrängen (exklusive hinder). Våra algoritmer fungerar antingen för godtycklig terräng (om någon av parametrarna A eller k är känd) eller för c-fett terräng, där c är någon konstant (okänd för roboten) och ingen ytterligare kunskap antas. T med hinder är c-fett om R/r ≤ c, där R är radien av den minsta skivan som innehåller T och r är radien av den största skivan som finns i T.) Vi visar också en matchande nedre gräns  på komplexiteten av prospektering för begränsad sikt, även om terrängen är känd för roboten.
Kostnaden för prospektering av godtyckliga terränger med hinder, både för begränsad och obegränsad vision, studerades i REF.
Worst-case optimal exploration of terrains with obstacles
{'venue': 'Inf. Comput.', 'journal': 'Inf. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}