{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/44500"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/44500","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Combinatorial structures and filter design in information spaces","abstract":"Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-03-18T15:56:28Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jingjin.Yu.Thesis.pdf: 5836747 bytes, checksum: 3eb6d3859f8759ae7f5b8aea14208ae1 (MD5)","abstract_html":"Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-03-18T15:56:28Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jingjin.Yu.Thesis.pdf: 5836747 bytes, checksum: 3eb6d3859f8759ae7f5b8aea14208ae1 (MD5)","abstract_has_math":false,"creators":["Yu, Jingjin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["LaValle, Steven M.","Hutchinson, Seth A.","Liberzon, Daniel M.","Mitra, Sayan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-05-24T22:18:24Z","date_published":"2013-05-24T22:18:24Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Combinatorial Filter","Shadow Information Spaces","Sensor Fusion","Situation Awareness"],"languages":["en"],"rights":["Copyright 2013 Jingjin Yu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/44500","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["LaValle, Steven M.","Hutchinson, Seth A.","Liberzon, Daniel M.","Mitra, Sayan"]},{"key":"dc:creator","label":"Author","values":["Yu, Jingjin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-05-24T22:18:24Z","2015-05-24T10:01:30Z","2013-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorial Filter","Shadow Information Spaces","Sensor Fusion","Situation Awareness"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Jingjin Yu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/44500"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-03-18T15:56:28Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jingjin.Yu.Thesis.pdf: 5836747 bytes, checksum: 3eb6d3859f8759ae7f5b8aea14208ae1 (MD5)","Made available in DSpace on 2013-05-24T22:18:24Z (GMT). No. of bitstreams: 2 Jingjin_Yu.pdf: 5836810 bytes, checksum: 112d36994eb17d5415182a6093f244d7 (MD5) license.txt: 4057 bytes, checksum: 62ef47d817676f2897c939160fb13c5a (MD5)","Restriction data tranferred 2014-07-01T11:36:22-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2015-05-24 17:18:31 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (srobbins@illinois.edu) on 2013-05-24T22:19:30Z Item is restricted until 2015-05-24T22:18:31Z","U of I Only Restriction Lifted for Item 44473 on 2015-05-24T10:01:30Z.","In this thesis, we develop a filtering process called combinatorial filters for handling combinatorial processes that evolve over time and study two practical problems using this method. The first problem is a generalization of the sensing aspect of visibility-based pursuit evasion games, in which the task is to maintain the distribution of hidden targets that move outside the field of view while a sensor sweep is being performed. For this problem, we apply information space concepts to significantly reduce the general complexity so that information is processed only when the shadow region (all points invisible to the sensors) changes combinatorially or targets pass in and out of the field of view. The cases of distinguishable, partially distinguishable, and completely indistinguishable targets are handled. Depending on whether the targets move nondeterministically or probabilistically, more specific classes of problems are formulated. For each case, efficient filtering algorithms are introduced, implemented, and demonstrated that provide critical information for tasks such as counting, herding, pursuit-evasion, and situational awareness. Next, we study the problem of using sparse, heterogeneous sensor data to verify the stories (i.e., path samples) of agents. Since there are two sets of data, the combinatorial filter for this problem can be built in two ways: Using a filter (an automaton) built from sensor data to process the story or using a filter built from the story to process the sensor data. Both approaches lead to dynamic programming based efficient algorithms for extracting a compatible path if one exists. In addition to exact path inference, our method also applies to approximate path inference that allows errors in data. Besides immediate applicability toward security and forensics problems, the idea of behavior validation using external sensors also appears promising in complementing design time model verification."]},{"key":"dc:title","label":"Title","values":["Combinatorial structures and filter design in information spaces"]}]}],"canonical_facts":{"dc:contributor":["LaValle, Steven M.","Hutchinson, Seth A.","Liberzon, Daniel M.","Mitra, Sayan"],"dc:creator":["Yu, Jingjin"],"dc:date":["2013-05-24T22:18:24Z","2015-05-24T10:01:30Z","2013-05"],"dc:description":["Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-03-18T15:56:28Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jingjin.Yu.Thesis.pdf: 5836747 bytes, checksum: 3eb6d3859f8759ae7f5b8aea14208ae1 (MD5)","Made available in DSpace on 2013-05-24T22:18:24Z (GMT). No. of bitstreams: 2 Jingjin_Yu.pdf: 5836810 bytes, checksum: 112d36994eb17d5415182a6093f244d7 (MD5) license.txt: 4057 bytes, checksum: 62ef47d817676f2897c939160fb13c5a (MD5)","Restriction data tranferred 2014-07-01T11:36:22-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2015-05-24 17:18:31 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (srobbins@illinois.edu) on 2013-05-24T22:19:30Z Item is restricted until 2015-05-24T22:18:31Z","U of I Only Restriction Lifted for Item 44473 on 2015-05-24T10:01:30Z.","In this thesis, we develop a filtering process called combinatorial filters for handling combinatorial processes that evolve over time and study two practical problems using this method. The first problem is a generalization of the sensing aspect of visibility-based pursuit evasion games, in which the task is to maintain the distribution of hidden targets that move outside the field of view while a sensor sweep is being performed. For this problem, we apply information space concepts to significantly reduce the general complexity so that information is processed only when the shadow region (all points invisible to the sensors) changes combinatorially or targets pass in and out of the field of view. The cases of distinguishable, partially distinguishable, and completely indistinguishable targets are handled. Depending on whether the targets move nondeterministically or probabilistically, more specific classes of problems are formulated. For each case, efficient filtering algorithms are introduced, implemented, and demonstrated that provide critical information for tasks such as counting, herding, pursuit-evasion, and situational awareness. Next, we study the problem of using sparse, heterogeneous sensor data to verify the stories (i.e., path samples) of agents. Since there are two sets of data, the combinatorial filter for this problem can be built in two ways: Using a filter (an automaton) built from sensor data to process the story or using a filter built from the story to process the sensor data. Both approaches lead to dynamic programming based efficient algorithms for extracting a compatible path if one exists. In addition to exact path inference, our method also applies to approximate path inference that allows errors in data. Besides immediate applicability toward security and forensics problems, the idea of behavior validation using external sensors also appears promising in complementing design time model verification."],"dc:identifier":["http://hdl.handle.net/2142/44500"],"dc:language":["en"],"dc:rights":["Copyright 2013 Jingjin Yu"],"dc:subject":["Combinatorial Filter","Shadow Information Spaces","Sensor Fusion","Situation Awareness"],"dc:title":["Combinatorial structures and filter design in information spaces"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:34Z"}