Pruning and resampling of roadmap

[shaesaert]

Currently, the algorithm does not prune or resample the nodes for the roadmap of the rover. That is the algorithm operates as follows:

1. Samples random positions in the state-space of the rover
2. Builds sampling based roadmap
3. Computes value-function over this roadmap
4. Finished: Give simulation

The objective is to add a pruning and resampling step after the 3rd and to recompute the value function. Thus, 1->3 then resample and prune, iterate value function.

Suppose the result after step 2 is as follows:

Then based on the active choices of actions we can prune the transitions and nodes in this graph as follows: In this case we found the following:

  Nodes that can be pruned: [(-1, -1), ('0', 3), ('0', 13), ('0', 14), ('0', 15), ('0', 23), ('0', 24), ('0', 28), ('0', 31), ('0', 35), ('0', 36), ('0', 38)]
  number of active nodes = 29, percent of orig. nodes = 63 %
  number of active edges = 97, percent of orig. edges = 32 %

See https://github.com/pettni/pdf-abstraction/blob/ScalableBest_class_change/Demo_file/Rocksample.ipynb in commit b232d56ee88793c1233568f9a2196240bfdc54a1 .

[shaesaert]

I added a method to add a node to the firm graph https://github.com/pettni/pdf-abstraction/blob/b6545f9a30b61ceed8733e7913410750fb81689d/best/hVI_fsrm.py#L600 This automatically updates the firm graph nodes and edges and also the product structure. There is a unit test that uses it: https://github.com/pettni/pdf-abstraction/blob/b6545f9a30b61ceed8733e7913410750fb81689d/tests/test_det_roadmap.py#L197

[shaesaert]

I have also added a method to prune nodes in the product graph. Thus nodes are not pruned in Firm, since they are quite complicated to remove there. Instead, they are pruned from the product graph, this implies that they are no longer considered in the backups and for the value function

nodes, edges, visited = plot_optimizers(prod_,ax)
prod_.prune(keep_list=visited).

[shaesaert]

Solved : Pruning and resampling of way points

See commit March 2nd, 2019 Pruning:

• Nodes are pruned from both FIRM/Roadmap/Spath object and from the spec_Spath object.
• Nodes are removed from the sequence for backups spec_Spath.sequence
• Nodes that are of importance for some belief point will be kept

Resampling

• Nodes can be added with add_firm_nodes(#nodes, distance). The second variable gives the max distance of nodes the new node can be connected too.
• the nodes are first added in the roadmap Spath together with their new edges.
• the product roadmap spec_Spath is updated with the new nodes.
• the backup sequence spec_Spath.sequence is updated with the new nodes.

The result is as follows: The original roadmap (Spath)

The transitions that belong to the set of optimizers after 20 back-ups

The pruned and resampled (3 additional nodes) roadmap (SPath) with:

• nodes removed that cannot be reached from the initial state via any of the transitions (arrows) in the previous figure.
• nodes added via a uniform distribution

The transitions that belong to the set of optimizers after 5 additional back-ups The backups start with the values of the initial specs_Spath in which the new nodes get value zero. Already after a couple of backups this means that a shorter path is found in case the first sample region is not sufficient. This reduces the needed path length from 20 to 12. Ofcourse this also implies that the overall risk discreases.