Combinatorial Filters

Abstract

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 sensing modalities. 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.