存在一个博弈,其状态由布尔变量p_1
、p_2
、...、p_n
n
量化。假设0 <= n <= 10
.游戏的目的是跟踪尽可能多的变量的状态,以及它们何时会改变状态(见下文(。
一次只能观察到变量的子集。当一个变量的状态从true
变为false
时,我们总是被告知,但只有当所讨论的变量被观察到时,我们才会被告知哪个变量被改变了。
如果某些p_i
在t
时间将状态从true
更改为false
,那么它将在t + 60
时间将状态从false
更改回true
。
下面是一些示例情况和所需的行为。假设有三个变量,p_1
、p_2
和p_3
。
- 所有变量都是可观察的。变量改变状态,通过观察,它是
p_1
。我们知道p_1
会在t + 60
时改变状态。 -
p_1
和p_2
是可观察到的。变量更改状态。应该推断它是p_3
.我们知道p_3
将在t + 60
时改变状态。 -
p_1
是可观察到的,并且已知p_2
在t - 30
时将状态更改为false
。变量更改状态。它没有通过观察p_1
,p_2
只会在t + 30
时将状态更改为true
,因此它被p_3
。 - 已知
p_1
t - 30
时将状态更改为false
,p_2
t - 75
时将状态更改为false
,p_3
在t - 80
时将状态更改为假。变量更改状态。在t + 1
p_2
观察到的值为true
。因为p_1
仍然是false
的,并且p_2
被观测到true
,所以应该推断p_3
是false
的,并且会在t + 60
时将状态改变回true
。 -
p_1
和p_2
是可观察到的。众所周知,p_3
在t - 70
时将状态更改为false
。没有变量更改状态。应该推断p_3
是正确的,因为它在t - 10
时会从false
变为true
,如果它从true
变为false
,我们将被告知变量变化的状态。
我尝试过的一种方法涉及在每次变量状态更改通知上迭代每个变量,并根据以下条件排除可能的匹配项:
- 它是否可见且未更改状态
- 它的最后一次状态更改是否已知,并且过去的时间还不够远,无法更改回来。
然后,对于状态已知的剩余变量,根据变量在特定状态下最后一次观察到的时间、变量可能已更改状态的时间(从 false
到 true
返回(等来确定其最后一个变量的上限和下限。然后,如果该边界内仅存在一个变量更改事件,则它应该是与该变量对应的事件。结果太麻烦了,我没有继续。每一行都是一个负担,因为似乎可能的状态组合数量太大,我不会考虑一些事情。
鉴于问题陈述,上述方法是否合理?有没有一种通用的方法来对这样的问题进行建模,以便更优雅地解决它们?
在@NicoSchertler的建议下,我想出了一个解决方案,通过基于Observations
和Hypotheses
序列创建状态集来处理不确定性。观测值是特定(观察到的(变量的已知状态,而假设是状态的通知,但没有关于它适用于哪个变量的信息。我们能够假设假设不能应用于正在观察的变量。此解决方案不处理启动状态未知(尚(的情况。
有一个单一的起始状态对应于每个变量都true
的情况。当提供hypothesis
时,通过假设每个未观测的变量是hypothesis
的主体,可能会产生多个(n
(后继状态。导致矛盾的继承国被抛弃。当提供observation
时,每个当前状态都会生成一个后继状态。任何导致矛盾的状态都被抛弃。通过这种方式,假设和观察的序列导致变量可能处于的一组可能状态。
出于我的特定目的,我想知道基于这些状态可以知道什么(而不是例如是否存在有效的解决方案(。将状态组合在一起,并返回一个结果,如果该变量在所有状态中具有相同的状态,则给出每个变量的状态。
考虑到n
状态和m
通知,最坏情况的复杂性是n^m
这可能非常有限,但对于我有限的应用程序来说应该没问题。
这是 JavaScript 实现和测试代码。
求解器.js
// Time for state to change back.
var STATE_CHANGE = 6e4;
// Possible notification lag.
var EPSILON = 2e3;
// Comparison operations.
function lt(a, b) {
return a - b < EPSILON;
}
function gt(a, b) {
return b - a < EPSILON;
}
function eq(a, b) {
return Math.abs(a - b) < EPSILON;
}
// Object clone.
function clone(obj) {
return JSON.parse(JSON.stringify(obj));
}
module.exports = Solver;
/**
* Solver solves boolean dynamic state.
* @param {Array<string>} variables - array of variable names.
*/
function Solver(variables) {
this.variables = {};
this.states = [];
this._time = null;
var state = {};
var time = Date.now();
var self = this;
// TODO: Handle unknown or variable start.
variables.forEach(function (variable) {
self.variables[variable] = {
observed: false
};
state[variable] = {
state: true,
intervals: [{
state: true,
start: time,
observed: false,
end: null
}]
};
});
this.states.push(state);
}
// Set subset of variables as observed, the rest assumed not.
Solver.prototype.setObserved = function(variables) {
var unobserved_variables = Object.keys(this.variables).filter(function (variable) {
return variables.indexOf(variable) === -1;
});
var self = this;
variables.forEach(function (variable) {
self.variables[variable].observed = true;
});
unobserved_variables.forEach(function (variable) {
self.variables[variable].observed = false;
});
};
// Hypothesis has time, state.
Solver.prototype.addHypothesis = function(h) {
this.updateVariables();
var states = [];
for (var i = 0; i < this.states.length; i++) {
var newStates = this.applyHypothesis(this.states[i], h);
if (newStates)
Array.prototype.push.apply(states, newStates);
}
this.states = states;
};
// Observation has time, state, variable.
Solver.prototype.addObservation = function(o) {
this.updateVariables();
var states = [];
for (var i = 0; i < this.states.length; i++) {
var newState = this.applyObservation(this.states[i], o);
if (newState)
states.push(newState);
}
this.states = states;
};
// Get set of possible states.
Solver.prototype.getStates = function() {
this.updateVariables();
return this.states.slice();
};
// Get consolidated state.
// Each variable has state (true|false|null), change (if false). change
// is number or array (if there is disagreement)
Solver.prototype.getState = function() {
this.updateVariables();
// Construct output.
var out = {};
var state = this.states[0];
for (var name in state) {
var variable = state[name];
if (variable.state) {
out[name] = {
state: variable.state
};
} else {
var time = variable.intervals[variable.intervals.length - 1].end;
out[name] = {
state: variable.state,
time: time
};
}
}
// Compare results across all states.
return this.states.slice(1).reduce(function (out, state) {
for (var name in out) {
var out_variable = out[name],
variable = state[name];
// Check for matching states.
if (out_variable.state === variable.state) {
// Falsy check time.
if (!out_variable.state) {
// TODO: check undefined in case interval not updated?
var change = variable.intervals[variable.intervals.length - 1].end;
if (out_variable.time instanceof Array) {
if (out_variable.time.indexOf(change) === -1) {
out_variable.push(change);
}
} else if (out_variable.time !== change) {
var times = [out_variable.time, change];
out_variable.time = times;
} // Else matches, so no problem.
}
} else {
// Conflicted states.
out_variable.state = null;
// In case it was set.
delete out_variable.time;
}
}
return out;
}, out);
};
// Update `false` state variables based on false end
// time, if present.
Solver.prototype.updateVariables = function() {
var time = this._time || Date.now();
for (var i = 0; i < this.states.length; i++) {
var state = this.states[i];
for (var name in state) {
var variable = state[name];
// Update changeback.
if (!variable.state) {
if (variable.intervals.length > 0) {
var last = variable.intervals[variable.intervals.length - 1];
if (last.end && last.end <= time) {
// update to true.
variable.state = true;
variable.intervals.push({
state: true,
start: time,
end: null
});
}
}
}
}
}
};
// Return state with observation applied or null if invalid.
Solver.prototype.applyObservation = function(state, observation) {
var variable = state[observation.variable];
if (variable.state && !observation.state) {
// Change in observed variable true -> false
variable.state = observation.state;
variable.intervals.push({
state: variable.state,
start: observation.time,
end: observation.time + STATE_CHANGE
});
return state;
} else if (variable.state && observation.state) {
// Expected state.
return state;
} else if (!variable.state && observation.state) {
// Potentially updating variable.
var time = variable.intervals[variable.intervals.length - 1];
if (eq(time, observation.time)) {
// update state.
variable.state = observation.state;
variable.intervals.push({
state: observation.state,
start: observation.time,
end: null
});
return state;
} else {
// Could not update this variable.
return null;
}
} else if (!variable.state && !observation.state) {
// Expected state.
return state;
}
};
// Returns multiple states or null if invalid
Solver.prototype.applyHypothesis = function(state, hypothesis) {
hypothesis = clone(hypothesis);
var states = [];
for (var name in state) {
// Skip observed variables, no guessing with them.
if (this.variables[name].observed)
continue;
var newState = clone(state);
var variable = newState[name];
// Hypothesis is always false.
if (variable.state) {
// Change in observed variable true -> false
variable.state = hypothesis.state;
variable.intervals.push({
state: variable.state,
start: hypothesis.time,
end: hypothesis.time + STATE_CHANGE
});
} else {
newState = null;
}
if (newState !== null) {
states.push(newState);
}
}
if (states.length === 0) {
return null;
} else {
return states;
}
};
测试求解器.js
var Solver = require('./solver');
var p_1 = "p_1",
p_2 = "p_2",
p_3 = "p_3";
var solver = new Solver([p_1, p_2, p_3]);
var t = Date.now();
solver.setObserved([p_1, p_2, p_3]);
solver._time = t + 5e3;
solver.addObservation({
variable: p_1,
state: false,
time: t + 5e3
});
var result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 65e3 &&
result[p_2].state &&
result[p_3].state) {
console.log("PASS: Test 1.");
} else {
console.log("FAIL: Test 1.");
}
solver = new Solver([p_1, p_2, p_3]);
solver.setObserved([p_1, p_2]);
solver._time = t + 5e3;
solver.addHypothesis({
state: false,
time: t + 5e3
});
result = solver.getState();
if (result[p_1].state &&
result[p_2].state &&
!result[p_3].state && result[p_3].time === t + 65e3) {
console.log("PASS: Test 2.");
} else {
console.log("FAIL: Test 2.");
}
solver = new Solver([p_1, p_2, p_3]);
solver.setObserved([p_1]);
solver._time = t - 30e3;
solver.addObservation({
variable: p_2,
time: t - 30e3,
state: false
});
solver._time = t;
solver.addHypothesis({
state: false,
time: t
});
var result = solver.getState();
if (result[p_1].state &&
!result[p_2].state && result[p_2].time === t + 30e3 &&
!result[p_3].state && result[p_3].time === t + 60e3) {
console.log("PASS: Test 3.");
} else {
console.log("FAIL: Test 3.");
}
solver = new Solver([p_1, p_2, p_3]);
solver._time = t - 80e3;
solver.addObservation({
variable: p_3,
time: t - 80e3,
state: false
});
solver._time = t - 75e3;
solver.addObservation({
variable: p_2,
time: t - 75e3,
state: false
});
solver._time = t - 30e3;
solver.addObservation({
variable: p_1,
time: t - 30e3,
state: false
});
solver._time = t;
solver.addHypothesis({
state: false,
time: t
});
result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 30e3 &&
result[p_2].state === null &&
result[p_3].state === null) {
console.log("PASS: Test 4.");
} else {
console.log("FAIL: Test 4.");
}
solver._time = t + 1;
solver.addObservation({
variable: p_2,
time: t + 1,
state: true
});
var result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 30e3 &&
result[p_2].state &&
!result[p_3].state && result[p_3].time === t + 60e3) {
console.log("PASS: Test 5.");
} else {
console.log("FAIL: Test 5.");
}