OCTOBER 2018 | VOL. 61 | NO. 10 | COMMUNICATIONS OF THE ACM 99 However, the drone may require drastic corrections whenever the control loop does run; in a sense, motion becomes more “nervous.” Small values of Prun limit the processing gains. However, control runs more often, ensuring the drone operates smoothly. We demonstrate that gains over time-triggered control are seen for many different settings of Prun; 7 therefore, tuning this parameter is typically no major issue.

Run-timea. The question is now how to realize the functionality above at run-time, and especially how to gather the data required to tune the logistic regression models. To that end, we initially run the control loop at fixed rate for a predefined limited time, tracking whether the actuator settings change. This gives us an initial data set to employ least square estimators to compute the parameters of logistic regression. From this point on, reactive control kicks in and drives the execution of the control logic based on whether the probability of new actuator settings, according to the logistic regression models, surpasses Prun.

False positives may occur when logistic regression triggers the execution of the control logic, yet the newly computed actuator settings stay the same. In this case, the change in the sensor reading is added to the data set initially used for tuning the regression models. The least square estimation repeats throughout the execution, as part of the best-effort scheduler part of the autopilot control loop, shown in Figure 2, taking false positives into account. Such a simple form of auto-tuning25 progressively improves the estimation accuracy over time. We discuss the case of false negatives next.

3. 2. Dealing with time

Problem. PID controllers used in autopilots are conceived under the assumption that sensors are sampled almost simultaneously and at a fixed rate. In reality, the time of sampling, and therefore of possibly recognizing the need to execute the control loop, is not necessarily aligned across sensors. Drastic changes in the sensor inputs may also be correlated. For example, when the accelerometers record a sudden increase because of a wind gust, a gyroscope also likely records significant changes. A traditional implementation would process these inputs together.

Approach. We take a conservative approach to address these issues. Based on the sampling frequency of every sensor in the system, we compute the system’s hyperperiod as the smallest interval of time after which the sampling of all sensors repeats. Upon recognizing first the conditions requiring the execution of the control loop, we wait until the current hyperperiod completes. This allows us to “accumulate” all inputs on different sensors, giving the most up-to-date inputs to the control logic at once.

Moreover, we need to cater for situations where false
negatives happen in a row, potentially threatening
something just happened in the environment that requires
the drone to react. However, what is a “significant” change
in the sensor readings depends on several factors, including
the accuracy of sensor hardware, the physical characteristics
of the drone, and the actual control logic.

Approach. Our solution abstracts away from these aspects: despite the control logic is deterministic, we consider a change in the control output as a random phenomena. The input to this phenomena is the difference between consecutive samples of the same navigation sensor; the output is a binary value indicating whether the actuator settings need to change. If so, we need to run the control loop to compute the new settings. Therefore, an accurate statistical estimator of such random phenomena would allow us to take an informed decision on whether to run the control loop.

Among estimators with a binary dependent variable, logistic regression, 12 shown in Figure 4 in its general form, closely matches this intuition. For small changes in the sensor inputs, the probability of changes in the actuator settings is small. When changes in sensor inputs are large, a change in the actuator settings becomes (almost) certain. It also turns out it is possible estimate the parameters shaping the curve of Figure 4 efficiently, because logistic regression allows one to employ traditional estimators, such as least squares. 12

Operation. We employ one logistic regression model per navigation sensor. Given a change in the sensor readings, we compute the probability that the change corresponds to new control decisions, according to a corresponding logistic regression model. If this is greater than a threshold Prun, we execute the control logic, with all other inputs set to the most recent value; otherwise, we maintain the earlier output to the actuators.

This approach assumes that changes in a sensor’s inputs at different times are statistically independent. This is justified because the time-dependent I, D components of the PID controllers bear little influence in our setting, as discussed earlier. Moreover, maintaining the earlier output to the actuators is possible only as long as the control set-point does not change in the mean time. This is most often the case when drones hover or perform waypoint navigation, but rarely happens in applications such as aerial acrobatics, where this approach would probably be inefficient.

Parameter Prun offers a knob to trade processing resources with the tightness of control. Large values of Prun spare a significant fraction of control executions.

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

No input changes Large input changes Logistic

Figure 4. Example logistic function.

a Note that this design considers the initial drone execution as representative of the rest of the flight. Should this not be the case, a fail-over mechanism kicks in that recomputes the logistic regression parameters from scratch.