{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:20:28Z","timestamp":1737091228899,"version":"3.33.0"},"reference-count":12,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":4699,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1994,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the target\u2010reaching problem in plane scenes for a point robot which has a tactile sensor and can locate the target ray. It might have a compass, too, but it is not able to perceive the coordinates of its position nor to measure distances. The complexity of an algorithm is measured by the number of straight moves until reaching the target, as a function of the number of vertices of the (polygonal) scene. It is shown how the target point can be reached by exhaustive search without using a compass, with the complexity exp(<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>)). Using a compass, there is a target\u2010reaching algorithm, based on rotation counting, with the complexity<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>). The decision problem, to recognize if the target cannot be reached because it belongs to an obstacle, cannot be solved by our type of robot. If the behaviour of a robot without compass is periodic in a homogeneous environment, it cannot solve the target\u2010reaching problem.<\/jats:p><jats:p><jats:bold>Mathematics Subject Classification:<\/jats:bold>68Q20, 68U05, 03D15.<\/jats:p>","DOI":"10.1002\/malq.19940400210","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T17:20:40Z","timestamp":1180200040000},"page":"237-260","source":"Crossref","is-referenced-by-count":0,"title":["Navigation Without Perception of Coordinates and Distances"],"prefix":"10.1002","volume":"40","author":[{"given":"Armin","family":"Hemmerling","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"203","article-title":"Bemerkungen zum Labyrinth\u2010Problem","volume":"15","author":"Asser G.","year":"1977","journal-title":"Elektron. Informationsverarb. Kybernet."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19780860120"},{"key":"e_1_2_1_4_2","unstructured":"Bar\u2010Eli E. P.Berman A.Fiat andP.Yan On\u2010line navigation in a room. 3rd SODA 1992 237\u2013249."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"Blum M. andD.Kozen On the power of compass. 19th FOCS 1978 132\u2013142.","DOI":"10.1109\/SFCS.1978.30"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"Blum A. P.Raghavan andB.Schieber Navigation in unfamiliar geometric terrain. 23rd STOC 1991 494\u2013504.","DOI":"10.1145\/103418.103419"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"Deng X. T.Kameda andC.Papadimitriou How to learn an unknown environment. 32nd FOCS 1991 298\u2013303.","DOI":"10.1109\/SFCS.1991.185382"},{"volume-title":"Labyrinth Problems \u2014 Labyrinth\u2010Searching Abilities of Automata","year":"1989","author":"Hemmerling A.","key":"e_1_2_1_8_2"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136037"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"Klein R. Walking an unknown street with bounded detour. 32nd FOCS 1991 304\u2013313.","DOI":"10.1109\/SFCS.1991.185383"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"Lumelsky V. J. andA. A.Stepanov Path\u2010planning strategies for a mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica1987 2 403\u2013430.","DOI":"10.1007\/BF01840369"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90263-2"},{"key":"e_1_2_1_13_2","first-page":"95","volume-title":"Algorithmic and Geometric Aspects of Robotics","author":"Yap C.\u2010K.","year":"1987"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19940400210","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19940400210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:20:57Z","timestamp":1737051657000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19940400210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1002\/malq.19940400210"],"URL":"https:\/\/doi.org\/10.1002\/malq.19940400210","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}