TY - JOUR
T1 - Combinatorial filters
T2 - Sensor beams, obstacles, and possible paths
AU - Tovar, Benjamin
AU - Cohen, Fred
AU - Bobadilla, Leonardo
AU - Czarnowski, Justin
AU - Lavalle, Steven M.
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014/4
Y1 - 2014/4
N2 - A problem is introduced in which a moving body (robot, human, animal, vehicle, and so on) travels among obstacles and binary detection beams that connect between obstacles or barriers. Each beam can be viewed as a virtual sensor that may have many possible alternative implementations. The task is to determine the possible body paths based only on sensor observations that each simply report that a beam crossing occurred. This is a basic filtering problem encountered in many settings, under a variety of sensingmodalities. Filtering methods are presented that reconstruct the set of possible paths at three levels of resolution: (1) the possible sequences of regions (bounded by beams and obstacles) visited, (2) equivalence classes of homo-topic paths, and (3) the possible numbers of times the path winds around obstacles. In the simplest case, all beams are disjoint, distinguishable, and directed. More complex cases are then considered, allowing for any amount of beams overlapping, indistinguishability, and lack of directional information. The method was implemented in simulation. An inexpensive, low-energy, easily deployable architecture was also created which implements the beam model and validates the methods of the article with experiments.
AB - A problem is introduced in which a moving body (robot, human, animal, vehicle, and so on) travels among obstacles and binary detection beams that connect between obstacles or barriers. Each beam can be viewed as a virtual sensor that may have many possible alternative implementations. The task is to determine the possible body paths based only on sensor observations that each simply report that a beam crossing occurred. This is a basic filtering problem encountered in many settings, under a variety of sensingmodalities. Filtering methods are presented that reconstruct the set of possible paths at three levels of resolution: (1) the possible sequences of regions (bounded by beams and obstacles) visited, (2) equivalence classes of homo-topic paths, and (3) the possible numbers of times the path winds around obstacles. In the simplest case, all beams are disjoint, distinguishable, and directed. More complex cases are then considered, allowing for any amount of beams overlapping, indistinguishability, and lack of directional information. The method was implemented in simulation. An inexpensive, low-energy, easily deployable architecture was also created which implements the beam model and validates the methods of the article with experiments.
UR - http://www.scopus.com/inward/record.url?scp=84900528955&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84900528955&partnerID=8YFLogxK
U2 - 10.1145/2594767
DO - 10.1145/2594767
M3 - Article
AN - SCOPUS:84900528955
VL - 10
JO - ACM Transactions on Sensor Networks
JF - ACM Transactions on Sensor Networks
SN - 1550-4859
IS - 3
M1 - 47
ER -