← Back to the chapter · Previous detail · Next detail →

Technical detail · ACE and Shared Context Sensing

Compare conditional sensing plans

14.11 Sensing-Planner Complexity and a Practical Heuristic

A conditional sensing plan is a decision tree. An internal node tests a cached attribute, wakes a sensor or runs an inference; each edge represents a result. A leaf returns context with explicit confidence and freshness. For node aa, cost c(a)c(a) and outcomes vv,

J(a)=c(a)+∑vP(v∣a)J(next(a,v)).J(a)=c(a)+\sum_v P(v\mid a)J(\text{next}(a,v)).

At a terminal leaf, J=0J=0 only when evidence is sufficient. Otherwise another test or authoritative fallback is required. Consider InMeeting:

First testTest energyResolves requestUnresolved fallbackExpected plan cost
Time-window rule0.02 mJ20%2.0 mJ0.02+0.80(2.0)=1.620.02+0.80(2.0)=1.62 mJ
Accelerometer classifier0.30 mJ75%2.0 mJ0.30+0.25(2.0)=0.800.30+0.25(2.0)=0.80 mJ
Acquire all sensors2.0 mJ100%02.0 mJ

The time rule is the cheapest test, but the accelerometer yields the cheaper plan. Obtain outcome probabilities from representative traces; invented confidence values make the optimization misleading.

With nn optional attributes, there are 2n2^n subsets and n!n! full orderings, with different choices after each outcome. General optimal decision-tree and related sensing-plan formulations contain known NP-hard problems. Small constrained instances can still be searched exactly. Branch-and-bound stops expanding a partial tree when accumulated cost plus an optimistic lower bound exceeds the best complete plan found.

← Back to the chapter · Previous detail · Next detail →