Search for: All records

Probabilistic Simple Temporal Networks (PSTN) facilitate solving many interesting scheduling problems by characterizing uncertain task durations with unbounded probabilistic distributions. However, most current approaches assess PSTN performance using normal or uniform distributions of temporal uncertainty. This paper explores how well such approaches extend to families of non-symmetric distributions shown to better represent the temporal uncertainty introduced by, e.g., human teammates by building new PSTN benchmarks. We also build probability-aware variations of current approaches that are more reactive to the shape of the underlying distributions. We empirically evaluate the original and modified approaches over well-established PSTN datasets. Our results demonstrate that alignment between the planning model and reality significantly impacts performance. While our ideas for augmenting existing algorithms to better account for human-style uncertainty yield only marginal gains, our results surprisingly demonstrate that existing methods handle positively-skewed temporal uncertainty better. 

Despite an increasing number of successful interventions designed to broaden participation in computing research, there is still significant attrition among historically marginalized groups in the computing research pipeline. This experience report describes a first-of-its-kind Undergraduate Consortium (UC; https://aaai-uc.github.io/about) that addresses this challenge by empowering students with a culmination of their undergraduate research in a conference setting. The UC, conducted at the AAAI Conference on Artificial Intelligence (AAAI), aims to broaden participation in the AI research community by recruiting students, particularly those from historically marginalized groups, supporting them with mentorship, advising, and networking as an accelerator toward graduate school, AI research, and their scientific identity. This paper presents our program design, inspired by a rich set of evidence-based practices, and a preliminary evaluation of the first years that points to the UC achieving many of its desired outcomes. We conclude by discussing insights to improve our program and expand to other computing communities. 

Fluency---described as the ``coordinated meshing of joint activities between members of a well-synchronized team''---is essential to human-robot team success. Human teams achieve fluency through rich, often mostly implicit, communication. A key challenge in bridging the gap between industry and academia is understanding what influences human perception of a fluent team experience to better optimize human-robot fluency in industrial environments. This paper addresses this challenge by developing an online experiment featuring videos that vary the timing of human and robot actions to influence perceived team fluency. Our results support three broad conclusions. First, we did not see differences across most subjective fluency measures. Second, people report interactions as more fluent as teammates stay more active. Third, reducing delays when humans' tasks depend on robots increases perceived team fluency. 

When communication between teammates is limited to observations of each other's actions, agents may need to improvise to stay coordinated. Unfortunately, current methods inadequately capture the uncertainty introduced by a lack of direct communication. This paper augments existing frameworks to introduce Simple Temporal Networks for Improvisational Teamwork (STN-IT)—a formulation that captures both the temporal dependencies and uncertainties between agents who need to coordinate but lack reliable communication. We define the notion of strong controllability for STN-ITs, which establishes a static scheduling strategy for controllable agents that produces a consistent team schedule, as long as non-communicative teammates act within known problem constraints. We provide both an exact and approximate approach for finding strongly controllable schedules, empirically demonstrate the trade-offs between these approaches on benchmarks of STN-ITs, and show analytically that the exact method is correct. 

When communication between teammates is limited to observations of each other’s actions, agents may need to improvise to stay coordinated. Unfortunately, current methods inadequately capture the uncertainty introduced by a lack of direct communication. This paper augments existing frameworks to introduce Simple Temporal Networks for Improvisational Teamwork (STN-IT) — a formulation that captures both the temporal dependencies and uncertainties between agents who need to coordinate, but lack reliable communication. We define the notion of strong controllability for STN-ITs, which establishes a static scheduling strategy for controllable agents that produces a consistent team schedule, as long as non-communicative teammates act within known problem constraints. We provide both an exact and approximate approach for finding strongly controllable schedules, empirically demonstrate the trade-offs between these two approaches on a benchmark of STN-ITs, and show analytically that the exact method is correct. In addition, we provide an empirical analysis of the exact and approximate approaches’ efficiency 

The controllability of a temporal network is defined as an agent's ability to navigate around the uncertainty in its schedule and is well-studied for certain networks of temporal constraints. However, many interesting real-world problems can be better represented as Probabilistic Simple Temporal Networks (PSTNs) in which the uncertain durations are represented using potentially-unbounded probability density functions. This can make it inherently impossible to control for all eventualities. In this paper, we propose two new dynamic controllability algorithms that attempt to maximize the likelihood of successfully executing a schedule within a PSTN. The first approach, which we call Min-Loss DC, finds a dynamic scheduling strategy that minimizes loss of control by using a conflict-directed search to decide where to sacrifice the control in a way that optimizes overall success. The second approach, which we call Max-Gain DC, works in the other direction: it finds a dynamically controllable schedule and then attempts to progressively strengthen it by capturing additional uncertainty. Our approaches are the first known that work by finding maximally dynamically controllable schedules. We empirically compare our approaches against two existing PSTN offline dispatch approaches and one online approach and show that our Min-Loss DC algorithm outperforms the others in terms of maximizing execution success while maintaining competitive runtimes. 

Automated scheduling is potentially a very useful tool for facilitating efficient, intuitive interactions between a robot and a human teammate. However, a current gap in automated scheduling is that it is not well understood how to best represent the timing uncertainty that human teammates introduce. This paper attempts to address this gap by designing an online human-robot collaborative packaging game that we use to build a model of human timing uncertainty from a population of crowdworkers. We conclude that heavy-tailed distributions are the best models of human temporal uncertainty, with a Log-Normal distribution achieving the best fit to our experimental data. We discuss how these results along with our collaborative online game will inform and facilitate future explorations into scheduling for improved human-robot fluency. 

Fluency is an important metric in Human-Robot Interaction (HRI) that describes the coordination with which humans and robots collaborate on a task. Fluency is inherently linked to the timing of the task, making temporal constraint networks a promising way to model and measure fluency. We show that the Multi-Agent Daisy Temporal Network (MAD-TN) formulation, which expands on an existing concept of daisy-structured networks, is both an effective model of human-robot collaboration and a natural way to measure a number of existing fluency metrics. The MAD-TN model highlights new metrics that we hypothesize will strongly correlate with human teammates' perception of fluency. 

Flexibility is a useful and common metric for measuring the amount of slack in a Simple Temporal Network (STN) solution space. We extend this concept to specific schedules within an STN’s solution space, developing a related notion of durability that captures an individual schedule’s ability to withstand disturbances and still remain valid. We identify practical sources of scheduling disturbances that motivate the need for durable schedules, and create a geometricallyinspired empirical model that enables testing a given schedule’s ability to withstand these disturbances. We develop a number of durability metrics and use these to characterize and compute specific schedules that we expect to have high durability. Using our model of disturbances, we show that our durability metrics strongly predict a schedule’s resilience to practical scheduling disturbances. We also demonstrate that the schedules we identify as having high durability are up to three times more resilient to disturbances than an arbitrarily chosen schedule is.