{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:44:49Z","timestamp":1760708689944,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T00:00:00Z","timestamp":1396310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR0011-05-1-0008"],"award-info":[{"award-number":["HR0011-05-1-0008"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-09-1-1052"],"award-info":[{"award-number":["N00014-09-1-1052"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0904501 (IIS Robotics) and 1035345 (Cyberphysical Systems)"],"award-info":[{"award-number":["0904501 (IIS Robotics) and 1035345 (Cyberphysical Systems)"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["0904501 (IIS Robotics) and 1035345 (Cyberphysical Systems)"],"award-info":[{"award-number":["0904501 (IIS Robotics) and 1035345 (Cyberphysical Systems)"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2014,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2594767","type":"journal-article","created":{"date-parts":[[2014,5,13]],"date-time":"2014-05-13T12:18:28Z","timestamp":1399983508000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Combinatorial Filters"],"prefix":"10.1145","volume":"10","author":[{"given":"Benjamin","family":"Tovar","sequence":"first","affiliation":[{"name":"Northwestern University, IL"}]},{"given":"Fred","family":"Cohen","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY"}]},{"given":"Leonardo","family":"Bobadilla","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Miami, FL"}]},{"given":"Justin","family":"Czarnowski","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}]},{"given":"Steven M.","family":"Lavalle","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}]}],"member":"320","published-online":{"date-parts":[[2014,5,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030194.1015482"},{"volume-title":"Proceedings of the Conference on Robotics: Science and Systems.","author":"Bobadilla L.","key":"e_1_2_1_2_1","unstructured":"L. Bobadilla , O. Sanchez , J. Czarnowski , K. Gossman , and S. M. Lavalle . 2011a. Controlling wild bodies using linear temporal logic . In Proceedings of the Conference on Robotics: Science and Systems. L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. Lavalle. 2011a. Controlling wild bodies using linear temporal logic. In Proceedings of the Conference on Robotics: Science and Systems."},{"volume-title":"Proceedings of the IEEE International Conference on Intelligent Robots and Systems.","author":"Bobadilla L.","key":"e_1_2_1_3_1","unstructured":"L. Bobadilla , O. Sanchez , J. Czarnowski , and S. M. Lavalle . 2011b. Minimalist multiple target tracking using directional sensor beams . In Proceedings of the IEEE International Conference on Intelligent Robots and Systems. L. Bobadilla, O. Sanchez, J. Czarnowski, and S. M. Lavalle. 2011b. Minimalist multiple target tracking using directional sensor beams. In Proceedings of the IEEE International Conference on Intelligent Robots and Systems."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513421"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.795798"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.928558"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"volume-title":"Papers on Group Theory and Topology","author":"Dehn M.","key":"e_1_2_1_9_1","unstructured":"M. Dehn . 1987. Papers on Group Theory and Topology . Springer . M. Dehn. 1987. Papers on Group Theory and Topology. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(96)00142-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279201"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.03.003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"D. B. A. Epstein M. S. Paterson G. W. Camon D. F. Holt S. V. Levy and W. P. Thurston. 1992. Word Processing in Groups. A. K. Peters Natick MA.   D. B. A. Epstein M. S. Paterson G. W. Camon D. F. Holt S. V. Levy and W. P. Thurston. 1992. Word Processing in Groups. A. K. Peters Natick MA.","DOI":"10.1201\/9781439865699"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/56.800"},{"volume-title":"Proceedings of the AAAI National Conference on Artificial Intelligence.","author":"Gerkey B.","key":"e_1_2_1_16_1","unstructured":"B. Gerkey , S. Thrun , and G. Gordon . 2004. Clear the building: Pursuit-evasion with teams of robots . In Proceedings of the AAAI National Conference on Artificial Intelligence. B. Gerkey, S. Thrun, and G. Gordon. 2004. Clear the building: Pursuit-evasion with teams of robots. In Proceedings of the AAAI National Conference on Artificial Intelligence."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891840"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/281508.281528"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/79.985686"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"e_1_2_1_21_1","unstructured":"L. J. Guibas R. Motwani and P. Raghavan. 1995. The robot localization problem. In Algorithmic Foundations of Robotics K. Goldberg D. Halperin J.-C. Latombe and R. Wilson Eds. A. K. Peters Wellesley MA 269--282.   L. J. Guibas R. Motwani and P. Raghavan. 1995. The robot localization problem. In Algorithmic Foundations of Robotics K. Goldberg D. Halperin J.-C. Latombe and R. Wilson Eds. A. K. Peters Wellesley MA 269--282."},{"volume-title":"Cambridge University Press","author":"Hatcher A.","key":"e_1_2_1_22_1","unstructured":"A. Hatcher . 2002. Algebraic Topology . Cambridge University Press , Cambridge, U.K. http:\/\/www.math.cornell.edu\/&sim;hatcher\/AT\/ATpage.html. A. Hatcher. 2002. Algebraic Topology. Cambridge University Press, Cambridge, U.K. http:\/\/www.math.cornell.edu\/&sim;hatcher\/AT\/ATpage.html."},{"key":"e_1_2_1_23_1","unstructured":"J. G. Hocking and G. S. Young. 1988. Topology. Dover New York.  J. G. Hocking and G. S. Young. 1988. Topology. Dover New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.3662552"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2006.870640"},{"volume-title":"Proceedings of the International Symposium on Advances in Robot Kinematics.","author":"Kim S.","key":"e_1_2_1_26_1","unstructured":"S. Kim , K. Sreenath , S. Bhattacharya , and V. Kumar . 2012. Trajectory planning for systems with homotopy class constraints . In Proceedings of the International Symposium on Advances in Robot Kinematics. S. Kim, K. Sreenath, S. Bhattacharya, and V. Kumar. 2012. Trajectory planning for systems with homotopy class constraints. In Proceedings of the International Symposium on Advances in Robot Kinematics."},{"volume-title":"Proceedings of the 4th International Symposium on Information Processing in Sensor Vetworks. IEEE Press, 40","author":"Kim W.","key":"e_1_2_1_27_1","unstructured":"W. Kim , K. Mechitov , J. Choi , and S. Ham . 2005. On target tracking with binary proximity sensors . In Proceedings of the 4th International Symposium on Information Processing in Sensor Vetworks. IEEE Press, 40 . W. Kim, K. Mechitov, J. Choi, and S. Ham. 2005. On target tracking with binary proximity sensors. In Proceedings of the 4th International Symposium on Information Processing in Sensor Vetworks. IEEE Press, 40."},{"volume-title":"Contributions to the Theory of Games","author":"Kuhn H. W.","key":"e_1_2_1_28_1","unstructured":"H. W. Kuhn . 1953. Extensive games and the problem of information . In Contributions to the Theory of Games , H. W. Kuhn and A. W. Tucker, Eds., Princeton University Press , Princeton, NJ , 196--216. H. W. Kuhn. 1953. Extensive games and the problem of information. In Contributions to the Theory of Games, H. W. Kuhn and A. W. Tucker, Eds., Princeton University Press, Princeton, NJ, 196--216."},{"key":"e_1_2_1_29_1","unstructured":"P. R. Kumar and P. Varaiya. 1986. Stochastic Systems. Prentice-Hall Englewood Cliffs NJ.  P. R. Kumar and P. Varaiya. 1986. Stochastic Systems. Prentice-Hall Englewood Cliffs NJ."},{"volume-title":"Planning Algorithms","author":"Lavalle S. M.","key":"e_1_2_1_30_1","unstructured":"S. M. Lavalle . 2006. Planning Algorithms . Cambridge University Press , Cambridge, U. K. http:\/\/planning.cs.uiuc.edu S. M. Lavalle. 2006. Planning Algorithms. Cambridge University Press, Cambridge, U. K. http:\/\/planning.cs.uiuc.edu"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1561\/2300000004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304981"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2010.2052273"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/332833.332838"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72665-4_36"},{"volume-title":"AAAI National Conference on Artificial Intelligence.","author":"Montemerlo M.","key":"e_1_2_1_36_1","unstructured":"M. Montemerlo , S. Thrun , D. Koller , and B. Wegbreit . 2002. FastSLAM: A factored solution to the simultaneous localization and mapping problem . In AAAI National Conference on Artificial Intelligence. M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. 2002. FastSLAM: A factored solution to the simultaneous localization and mapping problem. In AAAI National Conference on Artificial Intelligence."},{"volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation.","author":"O'Kane J. M.","key":"e_1_2_1_37_1","unstructured":"J. M. O'Kane and S. M. Lavalle . 2007. Sloppy motors, flaky sensors, and virtual dirt: Comparing imperfect, ill-informed robots . In Proceedings of the IEEE International Conference on Robotics and Automation. J. M. O'Kane and S. M. Lavalle. 2007. Sloppy motors, flaky sensors, and virtual dirt: Comparing imperfect, ill-informed robots. In Proceedings of the IEEE International Conference on Robotics and Automation."},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence.","author":"Parr R.","key":"e_1_2_1_38_1","unstructured":"R. Parr and A. Eliazar . 2003. DP-SLAM: Fast, robust simultaneous localization and mapping without predetermined landmarks . In Proceedings of the International Joint Conference on Artificial Intelligence. R. Parr and A. Eliazar. 2003. DP-SLAM: Fast, robust simultaneous localization and mapping without predetermined landmarks. In Proceedings of the International Joint Conference on Artificial Intelligence."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1859995.1860038"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1182807.1182833"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1182807.1182833"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906072252"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236427"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221051"},{"key":"e_1_2_1_45_1","unstructured":"S. Thrun W. Burgard and D. Fox. 2005. Probabilistic Robotics. MIT Press Cambridge MA. 30  S. Thrun W. Burgard and D. Fox. 2005. Probabilistic Robotics. MIT Press Cambridge MA. 30"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007436523611"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"B. Tovar F. Cohen and S. M. Lavalle. 2009. Sensor beams obstacles and possible paths. In Algorithmic Foundations of Robotics VIII G. Chirikjian H. Choset M. Morales and T. Murphey Eds. Springer 317--332.  B. Tovar F. Cohen and S. M. Lavalle. 2009. Sensor beams obstacles and possible paths. In Algorithmic Foundations of Robotics VIII G. Chirikjian H. Choset M. Morales and T. Murphey Eds. Springer 317--332.","DOI":"10.1007\/978-3-642-00312-7_20"},{"volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence.","author":"Tovar B.","key":"e_1_2_1_48_1","unstructured":"B. Tovar , L. Freda , and S. M. Lavalle . 2007a. Mapping and navigation from permutations of landmarks . In Proceedings of the 20th International Conference on Artificial Intelligence. B. Tovar, L. Freda, and S. M. Lavalle. 2007a. Mapping and navigation from permutations of landmarks. In Proceedings of the 20th International Conference on Artificial Intelligence."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2007.898962"},{"key":"e_1_2_1_50_1","unstructured":"J. Von Neumann and O. Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press Princeton NJ.  J. Von Neumann and O. Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press Princeton NJ."},{"volume-title":"Proceedings IEEE International Conference on Robotics and Automation.","author":"Yu J.","key":"e_1_2_1_51_1","unstructured":"J. Yu and S. M. Lavalle . 2008. Tracking hidden agents through shadow information spaces . In Proceedings IEEE International Conference on Robotics and Automation. J. Yu and S. M. Lavalle. 2008. Tracking hidden agents through shadow information spaces. In Proceedings IEEE International Conference on Robotics and Automation."},{"volume-title":"Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR'10)","author":"Yu J.","key":"e_1_2_1_52_1","unstructured":"J. Yu and S. M. Lavalle . 2010. Cyber detectives: Determining when robots or people misbehave . In Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR'10) . J. Yu and S. M. Lavalle. 2010. Cyber detectives: Determining when robots or people misbehave. In Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR'10)."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594767","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2594767","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:53Z","timestamp":1750230053000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594767"}},"subtitle":["Sensor Beams, Obstacles, and Possible Paths"],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["10.1145\/2594767"],"URL":"https:\/\/doi.org\/10.1145\/2594767","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2014,4]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}