|
|
 |
 |
 Energy Storage, Conversion And Utilization
 Energy Conservation, Consumption, And Utilization
|
 |
|
MAC versus PC: Determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains
Authors:
Wagner, I.A.
Lindenbaum, M.
Bruckstein, A.M.
|
| |
| Abstract: Three methods are described for exploring a continuous unknown planar region by a group of robots having limited sensors and no explicit communication. The authors formalize the problem, prove that its off-line version is NP-hard, and show a lower bound on the length of any solution. Then a deterministic mark and cover (MAC) algorithm is described for the on-line problem using short-lived navigational markers as a means of navigation and indirect communication. The convergence of the algorithm is proved, and its cover time is shown to be the asymptotically optimal O(A/a), where A is the total area and a is the area covered by the robot in a single step. The MAC algorithm is tested against an alternative randomized probabilistic covering (PC) method, which does not rely on sensors but is still able to cover an unknown region in an expected time that depends polynomially on the dimensions of the region. Both algorithms enable cooperation of several robots to achieve faster coverage. Finally, they show that the two methods can be combined to yield a third, hybrid algorithm with a better trade-off between performance and robustness. |
|
|
| Publication Date: |
01 Jan 2000
|
| Resource Type: |
Journal Article
|
| Resource Relation: |
International Journal of Robotics Research ; VOL. 19 ; ISSUE: 1 ; PBD: Jan 2000
|
| Research Organizations: |
IBM Haifa Research Lab., Matam (IL)
|
| Country of Publication: |
United States
|
| Language: |
English
|
|
|
|
|
|
|
 |
|
 |
|
|
Keywords relating to this report: 