Provable Methods for Searching with an Imperfect Sensor
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913537970929664 |
|---|---|
| author | Chakraborty, Nilanjan Kasthurirangan, Prahlad Narasimhan Mitchell, Joseph S. B. Nguyen, Linh Perk, Michael |
| author_facet | Chakraborty, Nilanjan Kasthurirangan, Prahlad Narasimhan Mitchell, Joseph S. B. Nguyen, Linh Perk, Michael |
| contents | Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times between points (e.g., based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to observe their performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06069 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Provable Methods for Searching with an Imperfect Sensor Chakraborty, Nilanjan Kasthurirangan, Prahlad Narasimhan Mitchell, Joseph S. B. Nguyen, Linh Perk, Michael Robotics Computational Geometry Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times between points (e.g., based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to observe their performance. |
| title | Provable Methods for Searching with an Imperfect Sensor |
| topic | Robotics Computational Geometry |
| url | https://arxiv.org/abs/2410.06069 |