A Scheduler for Actions with Iterated Durations

Authors

  • James Paterson Massachusetts Institute of Technology
  • Eric Timmons Massachusetts Institute of Technology
  • Brian Williams Massachusetts Institute of Technology

DOI:

https://doi.org/10.1609/aaai.v28i1.9046

Keywords:

Schedule, Loops, Preference, Optimization

Abstract

A wide range of robotic missions contain actions that exhibit looping behavior. Examples of these actions include picking fruit in agriculture, pick-and-place tasks in manufacturing and search patterns in robotic search or survey missions. These looping actions often have a range of acceptable values for the number of loops and a preference function over them. For example, during robotic survey missions, the information gain is expected to increase with the number of loops in a search pattern. Since these looping actions also take time, which is typically bounded, there is a challenge of maximizing utility while respecting time constraints. In this paper, we introduce the Looping Temporal Problem with Preference (LTPP) as a simple parameterized extension of a simple temporal problem. In addition, we introduce a scheduling algorithm for LTPPs which leverages the structure of the problem to find the optimal solution efficiently. We show more than an order of magnitude improvement in run-time over current scheduling techniques and framing a LTPP as a MINLP.

Downloads

Published

2014-06-21

How to Cite

Paterson, J., Timmons, E., & Williams, B. (2014). A Scheduler for Actions with Iterated Durations. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.9046