Generating and scheduling activities is particularly challenging
 when considering both consumptive resources and
 complex resource interactions such as time-dependent resource
 usage.We present three methods of determining valid
 temporal placement intervals for an activity in a temporally
 grounded plan in the presence of such constraints. We introduce
 the Max Duration and Probe algorithms which are
 sound, but incomplete, and the Linear algorithm which is
 sound and complete for linear rate resource consumption.
 We apply these techniques to the problem of scheduling
 awakes for a planetary rover where the awake durations
 are affected by existing activities. We demonstrate how the
 Probe algorithm performs competitively with the Linear algorithm
 given an advantageous problem space and well-defined
 heuristics. We show that the Probe and Linear algorithms
 outperform the Max Duration algorithm empirically.
 We then empirically present the runtime differences between
 the three algorithms. The Probe algorithm is currently base-lined
 for use in the onboard scheduler for NASA’s next planetary
 rover, the Mars 2020 rover. In many space missions, consumptive resources such as energy or data volume limit the number of activities that can be scheduled. These consumptive resources are oftentimes replenished periodically or gradually over time. For example, data is downlinked-replenishing data capacity-or energy is generated by solar panels or radioisotope thermoelectric generator (RTG) power supplies. The scheduler must therefore schedule activities while staying aware of resource replenishment in order to ensure that the resource state does not violate constraints (e.g. energy below a specified level or data buffers overflow). We focus on awake and asleep scheduling for a planetary rover, but our techniques generalize scheduling in the presence of complex consumptive resource activities.We focus on the onboard scheduler for NASA's next planetary rover, the Mars 2020 (M2020) rover (Jet Propulsion Laboratory 2018a) . Since the heart of our paper is awake and asleep scheduling, we concentrate on energy as the limit- ing consumptive resource. The M2020 rover's power source is a Multi-Mission Radioisotope Thermoelectric Generator (MMRTG) (Jet Propulsion Laboratory 2018b). The MM-RTG constantly generates energy for the rover's battery, but the CPU's awake and "idle" state (i.e. no other tasks) consumes more energy than the MMRTG provides. Therefore, the rover can only increase its energy, measured as battery state of charge (SOC), when the rover is asleep. The rover, however, must stay awake to not only execute activities, but also (re)-invoke the scheduler to generate a schedule. The M2020 onboard scheduler is responsible for generating and scheduling these awake periods.In order to generate and schedule awakes, the scheduler must compute valid start times for awakes and activities jointly to ensure that there is sufficient energy for both the awake and the activities. Each activity, however, requires varying awake sizes depending on existing awake periods and the activity's scheduled start time. If the activity is close to an existing awake, it may be necessary to extend an existing awake rather than generating a new awake as this would require the rover to shutdown and wakeup in quick succession ( Figure 1 ) which may lead to issues if the shutdown runs longer than nominally expected. Due to its varying duration, an awake's energy consumption and valid start times are challenging to determine.The remainder of the paper is organized as follows. First, we describe the timeline representation, which is also used by the M2020 onboard scheduler. We discuss calculating valid start time intervals-intervals in which starting the activity would not violate any constraints-and define the problem in relation to the timeline framework. Second, we discuss a general case-by-case approach to handling automatically generated awakes and the challenges specific cases pose. Third, we present three specific approaches to handling these challenges when generating and scheduling awakes: a) an over-conservative approach that always uses the maximum awake period potentially required by the activity when calculating valid intervals; b) a "probing" approach that only considers a single point in time rather than the entire interval; and c) a linear algebra approach that calculates exact valid intervals given the linear rate of energy replenishment and consumption. The "probing" approach is currently base-lined for the M2020 onboard scheduler. Fourth, we present empirical analysis to compare their de- Figure 1: When scheduling activity B, the scheduler should extend the existing awake rather than creating a new one to account for the possibility that the shutdown runs longer than nominally expected. W is a wakeup and S is a shutdown.grees of completeness and runtime performance. Lastly, we reference related works, describe future works, and discuss conclusions. Generating and scheduling activities in the presence of consumptive regenerative resources is especially challenging when a driving factor of feasibility of placement is dependent on interactions with the existing schedule. Scheduling activities and their awake periods is particularly challenging in the context of M2020 because the awake's duration is dependent on existing awakes. We presented three algorithms-Max Duration, Probe, and Linear-for scheduling awakes and analyzed their completeness and runtime. Despite being a locally sound and complete algorithm, the Linear algorithm was not always able to outperform in the global problem space. We demonstrated how a simple and incomplete algorithm can perform both suboptimally, as seen with the Max Duration algorithm, and also close to optimal, as seen with the Probe algorithm, dependent on the heuristic and input parameters. We showed that the Probe algorithm is a fair alternative to a more complete algorithm, especially considering its ease of implementation and runtime improvement.
This paper describes and analyzes three methods to schedule non-fixed duration activities in the presence of consumptive resources. The paper presents three approaches for on-board scheduling of activities in a planetary rover under reservoir resource constraints.