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: DREAM: An Algorithm for Mitigating the Overhead of Robust Rescheduling
Generating and executing temporal plans is difficult in uncertain environments. The current state-of-the-art algorithm for probabilistic temporal networks maintains a high success rate by rescheduling frequently as uncertain events are resolved, but this approach involves substantial resource overhead due to computing and communicating new schedules between agents. Aggressive rescheduling could thus reduce overall mission duration or success in situations where agents have limited energy or computing power, and may not be feasible when communication is limited. In this paper, we propose new approaches for heuristically deciding when rescheduling is most efficacious. We propose two compatible approaches, Allowable Risk and Sufficient Change, that can be employed in combination to compromise between the computation rate, the communication rate, and success rate for new schedules. We show empirically that both approaches allow us to gracefully trade success rate for lower computation and/or communication as compared to the state-of-the-art dynamic scheduling algorithm.  more » « less
Award ID(s):
1651822
PAR ID:
10134589
Author(s) / Creator(s):
; ; ; ; ; ; ;
Editor(s):
Benton, J; Lipovetzky, Nir; Onaindia, Eva; Smith, David E; Srivastava, Siddharth
Publisher / Repository:
AAAI Press, Palo Alto, California USA
Date Published:
Journal Name:
Proceedings of the International Conference on Automated Planning and Scheduling
Volume:
29
ISSN:
2334-0835
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; (, 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
  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. ; ; (, Electronics)
    null (Ed.)
    Intelligent utilization of resources and improved mission performance in an autonomous agent require consideration of cyber and physical resources. The allocation of these resources becomes more complex when the system expands from one agent to multiple agents, and the control shifts from centralized to decentralized. Consensus is a distributed algorithm that lets multiple agents agree on a shared value, but typically does not leverage mobility. We propose a coupled consensus control strategy that co-regulates computation, communication frequency, and connectivity of the agents to achieve faster convergence times at lower communication rates and computational costs. In this strategy, agents move towards a common location to increase connectivity. Simultaneously, the communication frequency is increased when the shared state error between an agent and its connected neighbors is high. When the shared state converges (i.e., consensus is reached), the agents withdraw to the initial positions and the communication frequency is decreased. Convergence properties of our algorithm are demonstrated under the proposed co-regulated control algorithm. We evaluated the proposed approach through a new set of cyber-physical, multi-agent metrics and demonstrated our approach in a simulation of unmanned aircraft systems measuring temperatures at multiple sites. The results demonstrate that, compared with fixed-rate and event-triggered consensus algorithms, our co-regulation scheme can achieve improved performance with fewer resources, while maintaining high reactivity to changes in the environment and system. 
    more » « less
  4. ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    null (Ed.)
    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
  5. ; ; (, IEEE)
    Deploying decentralized control strategies for outdoor multi-agent Uncrewed Aircraft Systems (UASs) is challenging due to timing variations, packet loss, and computing resource limitations. In this work we address robustness to these conditions through a novel co-regulated control strategy that varies the periodicity of control inputs and communication with other agents. Co-regulation is applied to a decentralized hierarchical controller consisting of a global component governing inter-group coordination to multiple targets while a local component governs intra-group coordination of the agents as they progress to the target of interest. The control gains are “gain scheduled” according to current conditions while a cyber controller schedules the control and communication tasks for execution based on swarm performance. The control gains are found via reinforcement learning and the entire algorithm is deployed on a swarm consisting of 7 custom agents. Our results show the impact of rethinking swarming algorithms with computation and communication resource limitations in mind and indicate we can provide exceptional swarm control utilizing fewer resources while also improving the quality of service for an onboard, anytime collision avoidance algorithm. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email