| dc.description.abstract | Given a pre-declared itinerary of potential activities and sites for sensor placement within an environment, sensor selection involves choosing a set of sensors which can determine whether what actually occurs matches the supplied itinerary. This problem is encountered when, subject to some budget, one instruments a facility in order to ensure that the agents within behave as expected (e.g., a laboratory where the robots operating inside should follow some policy). It also applies to settings that range from surveillance and security to the design of smart spaces. We tackle a variant of the sensor selection problem where multiple agents share the same environment, which introduces some modeling subtleties, including those arising from interactions. Specifically, the multi-agent validation problem may require more than merely the union of sensors necessary for individual agents owing to aliasing: different agents may trigger sensors without those sensors necessarily being able to distinguish who was the cause. Also, the treatment of time and modeling of interleaving becomes important in providing joint itineraries, especially when combining itineraries of individuals. Since the underlying problem is NP-hard, when multiple agents are considered, another of the issues is the natural increase in size of problem instances. This paper re-formulates sensor selection as a SAT problem and introduces a graph trimming technique based on a reachability analysis. Treating the problem as a question of satisfiability is especially apt when the primary interest is in determining whether the sensors that one has available (or are within some budget to purchase) have some arrangement that suffices to validate the itinerary of interest. It also facilitates use of fast, state-of-the-art solvers. Taken together, these modifications yield significant speed-up over the previous method, as we detail in our empirical results based on simple 2-agent case studies. | |
