To speed up the value iterations, we want to leverage the structure of the roadmap to speed up the backup operations. Additionally, we would like to have a useful metric based on which we can say that the value function has converged enough.
Structured back-ups
The order in which the algorithm performs backups over the nodes of the roadmap is of importance for the speed of convergence. Work on this topic can be found in https://arxiv.org/pdf/1401.3910.pdf.
In commit b232d56ee88793c1233568f9a2196240bfdc54a1, the backups are done in a reversed breadth-first graph recursion.
To do this, the commit b232d56ee88793c1233568f9a2196240bfdc54a1 differentiates itself of the original branch 5c6eb19 in a substantial way.
A graph is built that represents the reachable nodes in the product graph of the specification DFA and the roadmap.
From any node that contains a target node in the DFA, a virtual end node is added to the graph.
Starting from this endpoint, a reverse breadth-first list of graph nodes is composed.
The back-ups are computed in the order of this list of graph nodes.
Advance structured backups
It would be nice if we would be able to implement the methods from https://arxiv.org/pdf/1401.3910.pdf
to compute the ideal backup sequence.
Converged nodes versus converged graph
If a node and its neighbors did not change in the last backup, then we do not compute the backup. We refer to these nodes as converged. If all nodes in a graph have converged, then the graph has also converged.
As a criterion for convergence, we currently use the epsilon variable (default= 10**-5), if in average for a given node in the graph overall belief points the optimal value has changed less than epsilon we say that the node has converged.
To speed up the value iterations, we want to leverage the structure of the roadmap to speed up the backup operations. Additionally, we would like to have a useful metric based on which we can say that the value function has converged enough.
Structured back-ups
The order in which the algorithm performs backups over the nodes of the roadmap is of importance for the speed of convergence. Work on this topic can be found in https://arxiv.org/pdf/1401.3910.pdf. In commit b232d56ee88793c1233568f9a2196240bfdc54a1, the backups are done in a reversed breadth-first graph recursion. To do this, the commit b232d56ee88793c1233568f9a2196240bfdc54a1 differentiates itself of the original branch 5c6eb19 in a substantial way.
Advance structured backups
It would be nice if we would be able to implement the methods from https://arxiv.org/pdf/1401.3910.pdf to compute the ideal backup sequence.
Converged nodes versus converged graph
If a node and its neighbors did not change in the last backup, then we do not compute the backup. We refer to these nodes as converged. If all nodes in a graph have converged, then the graph has also converged.
As a criterion for convergence, we currently use the epsilon variable (default= 10**-5), if in average for a given node in the graph overall belief points the optimal value has changed less than epsilon we say that the node has converged.
TODO: Is there a way to formalize this?