skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Dynamic Control of Probabilistic Simple Temporal Networks
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.  more » « less
Award ID(s):
1651822
PAR ID:
10220621
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Proceedings of the AAAI Conference on Artificial Intelligence
Volume:
34
Issue:
06
ISSN:
2159-5399
Page Range / eLocation ID:
9851 to 9858
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Proceedings of the International Conference on Automated Planning and Scheduling)
    Benton, J; Lipovetzky, Nir; Onaindia, Eva; Smith, David E; Srivastava, Siddharth (Ed.)
    Controllability for Simple Temporal Networks with Uncertainty (STNUs) has thus far been limited to three levels: strong, dynamic, and weak. Because of this, there is currently no systematic way for an agent to assess just how far from being controllable an uncontrollable STNU is. We use a new geometric interpretation of STNUs to introduce the degrees of strong and dynamic controllability – continuous metrics that measure how far a network is from being controllable. We utilize these metrics to approximate the probabilities that an STNU can be dispatched successfully offline and online respectively. We introduce new methods for predicting the degrees of strong and dynamic controllability for uncontrollable networks. In addition, we show empirically that both metrics are good predictors of the actual dispatch success rate. 
    more » « less
  2. ; ; ; ; ; ; (, Proceedings of the International Conference on Automated Planning and Scheduling)
    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. 
    more » « less
  3. ; ; ; ; ; ; (, AAAI Spring Symposium Series on Can We Talk? How to Design Multi-Agent Systems In the Absence of Reliable Communications)
    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 
    more » « less
  4. ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    A Simple Temporal Network with Uncertainty (STNU) includes real-valued variables, called time-points; binary difference constraints on those time-points; and contingent links that represent actions with uncertain durations. STNUs have been used for robot control, web-service composition, and business processes. The most important property of an STNU is called dynamic controllability (DC); and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time-complexity is the RUL¯ algorithm due to Cairo, Hunsberger and Rizzi. Its complexity is O(mn + k²n + kn log n), where n is the number of time-points, m is the number of constraints, and k is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation. 
    more » « less
  5. ; (, Applied Mathematics & Optimization)
    In this paper, we consider initial boundary value problems and control problems for the wave equation on finite metric graphs with Dirichlet boundary controls. We propose new constructive algorithms for solving initial boundary value problems on general graphs and boundary control problems on tree graphs. We demonstrate that the wave equation on a tree is exactly controllable if and only if controls are applied at all or all but one of the boundary vertices. We find the minimal controllability time and prove that our result is optimal in the general case. The proofs for the shape and velocity controllability are purely dynamical, while the proof for the full controllability utilizes both dynamical and moment method approaches. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email