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: A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution
One area of research in multi-agent path finding is to determine how replanning can be efficiently achieved in the case of agents being delayed during execution. One option is to reschedule the passing order of agents, i.e., the sequence in which agents visit the same location. In response, we propose Switchable-Edge Search (SES), an A*-style algorithm designed to find optimal passing orders. We prove the optimality of SES and evaluate its efficiency via simulations. The best variant of SES takes less than 1 second for small- and medium-sized problems and runs up to 4 times faster than baselines for large-sized problems.  more » « less
Award ID(s):
2328671
PAR ID:
10628095
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
AAAI
Date Published:
Journal Name:
Proceedings of the International Conference on Automated Planning and Scheduling
Volume:
34
ISSN:
2334-0835
Page Range / eLocation ID:
201 to 209
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; (, Geography and Sustainability)
    A significant number and range of challenges besetting sustainability can be traced to the actions and interactions of multiple autonomous agents (people mostly) and the entities they create (e.g., institutions, policies, social network) in the corresponding social-environmental systems (SES). To address these challenges, we need to understand decisions made and actions taken by agents, the outcomes of their actions, including the feedbacks on the corresponding agents and environment. The science of complex adaptive systems—CAS science—has a significant potential to handle such challenges. We address the advantages of CAS science for sustainability by identifying the key elements and challenges in sustainability science, the generic features of CAS, and the key advances and challenges in modeling CAS. Artificial intelligence and data science combined with agent-based modeling promise to improve understanding of agents’ behaviors, detect SES structures, and formulate SES mechanisms. 
    more » « less
  2. (, Sociology of Education)
    Contradictory evidence of the relationship between education funding and student achievement could reflect heterogeneous effects by revenue source or student characteristics. This study examines potential heterogeneous effects of a particular type of local revenue—bond funds for capital investments—on achievement by socioeconomic status. Comparing California school districts within a narrow window on either side of the cutoff of voter support required to pass a general obligation bond measure, I use dynamic regression discontinuity models to estimate effects of passing a bond on academic achievement among low- and high-socioeconomic-status (SES) students. Results consistently suggest that passing a bond increases achievement among low- but not high-SES students. However, these benefits for low-SES students are delayed and emerge six years after an election. Effects are larger in low-income districts and in small districts, where benefits of capital investments are experienced by a larger proportion of students. 
    more » « less
  3. ; ; ; ; ; ; (, www.preprints.org)
    A significant number and range of challenges besetting sustainability can be traced to the actions and interactions of multiple autonomous agents (people mostly) and the entities they create (e.g., institutions, policies, social network) in the corresponding social-environmental systems (SES). To address these challenges, we need to understand decisions made and actions taken by agents, the outcomes of their actions, including the feedbacks on the corresponding agents and environment. The science of Agent-based Complex Systems—ACS science—has a significant potential to handle such challenges. The advantages of ACS science for sustainability are addressed by way of identifying the key elements and challenges in sustainability science, the generic features of ACS, and the key advances and challenges in modeling ACS. Artificial intelligence and data science promise to improve understanding of agents’ behaviors, detect SES structures, and formulate SES mechanisms. 
    more » « less
  4. ; ; ; (, European journal of operational research)
    We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents’ utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx). 
    more » « less
  5. ; ; ; (, Proceedings of the National Academy of Sciences)
    Effective management of social-ecological systems (SESs) requires an understanding of human behavior. In many SESs, there are hundreds of agents or more interacting with governance and regulatory institutions, driving management outcomes through collective behavior. Agents in these systems often display consistent behavioral characteristics over time that can help reduce the dimensionality of SES data by enabling the assignment of types. Typologies of resource-user behavior both enrich our knowledge of user cultures and provide critical information for management. Here, we develop a data-driven framework to identify resource-user typologies in SESs with high-dimensional data. To demonstrate policy applications, we apply the framework to a tightly coupled SES, commercial fishing. We leverage large fisheries-dependent datasets that include mandatory vessel logbooks, observer datasets, and high-resolution geospatial vessel tracking technologies. We first quantify vessel and behavioral characteristics using data that encode fishers’ spatial decisions and behaviors. We then use clustering to classify these characteristics into discrete fishing behavioral types (FBTs), determining that 3 types emerge in our case study. Finally, we investigate how a series of disturbances applied selection pressure on these FBTs, causing the disproportionate loss of one group. Our framework not only provides an efficient and unbiased method for identifying FBTs in near real time, but it can also improve management outcomes by enabling ex ante investigation of the consequences of disturbances such as policy actions. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email