More Like this

1. Path planning with Incremental Roadmap Update for Visibility-based Target Tracking

   https://doi.org/10.1109/IROS40897.2019.8967602  

   Laguna, Guillermo J.; Bhattacharya, Sourabh (November 2019, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))

   In this paper, we address the visibility-based target tracking problem in which a mobile observer moving along a p-route, which we define as a fixed path for target tracking, tries to keep a mobile target in its field-of-view. By drawing a connection to the watchman's route problem, we find a set of conditions that must be satisfied by the p-route. Then we propose a metric for tracking to estimate a sufficient speed for the observer given the geometry of the environment. We show that the problem of finding the p-route on which the observer requires minimum speed is computationally intractable. We present a technique to find a p-route on which the observer needs at most twice the minimum speed to track the intruder and a reactive motion strategy for the observer. 

   more » « less
2. Observer-Aware Legibility for Social Navigation

   https://doi.org/10.1109/RO-MAN53752.2022.9900676  

   Taylor, Ada V.; Mamantov, Ellie; Admoni, Henny (August 2022, EEE International Conference on Robot and Human Interactive Communication (RO-MAN))

   We designed an observer-aware method for creating navigation paths that simultaneously indicate a robot’s goal while attempting to remain in view for a particular observer. Prior art in legible motion does not account for the limited field of view of observers, which can lead to wasted communication efforts that are unobserved by the intended audience. Our observer-aware legibility algorithm directly models the locations and perspectives of observers, and places legible movements where they can be easily seen. To explore the effectiveness of this technique, we performed a 300-person online user study. Users viewed first-person videos of restaurant scenes with robot waiters moving along paths optimized for different observer perspectives, along with a baseline path that did not take into account any observer’s field of view. Participants were asked to report their estimate of how likely it was the robot was heading to their table versus the other goal table as it moved along each path. We found that for observers with incomplete views of the restaurant, observer-aware legibility is effective at increasing the period of time for which observers correctly infer the goal of the robot. Non-targeted observers have lower performance on paths created for other observers than themselves, which is the natural drawback of personalizing legible motion to a particular observer. We also find that an observer’s relationship to the environment (e.g. what is in their field of view) has more influence on their inferences than the observer’s relative position to the targeted observer, and discuss how this implies knowledge of the environment is required in order to effectively plan for multiple observers at once. 

   more » « less
3. Scalable Multi-Agent Surveillance: a Kernel-Based Approach

   https://doi.org/10.1109/ICRA55743.2025.11127616  

   Mandal, Shashwata; Bhattacharya, Sourabh (May 2025, IEEE)

   In this work, we address the deployment problem for a team of mobile guards that tries to maintain a line-ofsight with an unpredictable mobile intruder. First, we present a computationally efficient strategy for generating a set of points, called kernel points, that covers the entire polygon. We then introduce a polygon partitioning technique based on the location of the kernel points. Next, we propose control laws for a free guard to track an intruder in general polygonal environments based on the analysis of a pursuit-evasion game around a single corner [1]. Finally, we present several variations of the proposed control laws that include capture and search, and illustrate the improvement in the overall visual footprint of the team of mobile guards based on extensive simulations 

   more » « less
4. A Metric for Measuring the Impact of Rare Paths on Program Coverage

   https://doi.org/10.1109/SANER64311.2025.00042  

   Amour, Leo St; Tilevich, Eli; Gulzar, Muhammad Ali (March 2025, 2025 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER))

   Fuzzing has become a popular technique for discovering bugs and vulnerabilities. To increase the probability of finding bugs, developers should apply fuzzers that maximize program coverage. Program coverage typically measures the percentage of program lines or branches a fuzzer executes. However, these metrics fail to communicate the value of hitting a particular line, branch, or path. Many bugs manifest only within non-trivial control flows. To improve software quality, fuzzing non-trivial program paths should be more important than fuzzing trivial ones. This paper introduces rare-path coverage (RP-Coverage), a novel program coverage metric that conveys the value of discovering an unlikely control flow path. We have developed a new technique for estimating the probability of taking an execution path, which relies on probabilistic logic programming to declaratively express the logic for constructing and analyzing a probabilistic control flow graph. Our evaluation indicates RP-Coverage's promise as a metric for measuring fuzzing efficacy. Specifically, we observe that defects along rare paths-intuitively-substantially impact the effectiveness of fuzzers. However, we argue that existing fuzzing metrics fall short when conveying this significance. We also observe that the value of uncovering an unlikely path is better reflected by increases in RP-Coverage than existing metrics. Specifically, the average coverage increases are up to 49.5%, 11.1 %, and 15.4 % for RP-Coverage, line coverage, and branch coverage, respectively. This finding indicates that RP-Coverage is more elastic, or sensitive, to path probabilities and thus capable of more effectively quantifying a fuzzer's ability to discover unlikely program paths. As such, RP-Coverage demonstrates promise as a program coverage metric that enhances fuzzer fitness measures when supplementing standard criteria. 

   more » « less
5. The Bayesian Prophet: A Low-Regret Framework for Online Decision Making

   https://doi.org/10.1287/mnsc.2020.3624  

   Vera, Alberto; Banerjee, Siddhartha (March 2021, Management Science)

   null (Ed.)

   We develop a new framework for designing online policies given access to an oracle providing statistical information about an off-line benchmark. Having access to such prediction oracles enables simple and natural Bayesian selection policies and raises the question as to how these policies perform in different settings. Our work makes two important contributions toward this question: First, we develop a general technique we call compensated coupling, which can be used to derive bounds on the expected regret (i.e., additive loss with respect to a benchmark) for any online policy and off-line benchmark. Second, using this technique, we show that a natural greedy policy, which we call the Bayes selector, has constant expected regret (i.e., independent of the number of arrivals and resource levels) for a large class of problems we refer to as “online allocation with finite types,” which includes widely studied online packing and online matching problems. Our results generalize and simplify several existing results for online packing and online matching and suggest a promising pathway for obtaining oracle-driven policies for other online decision-making settings. This paper was accepted by George Shanthikumar, big data analytics. 

   more » « less