Combinatorial filters: Sensor beams, obstacles, and possible paths

Benjamin Tovar, Fred Cohen, Leonardo Bobadilla, Justin Czarnowski, Steven M. Lavalle

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number47
JournalACM Transactions on Sensor Networks
Issue number3
StatePublished - Apr 2014

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Combinatorial filters: Sensor beams, obstacles, and possible paths'. Together they form a unique fingerprint.

Cite this