## MSc\_Project

A repository for implementing NBS-algorithm and conducting experiments for the practical part of my master thesis.

#### Weekly Assignment

- Create more single goal problems.
- Keep up writing to follow up new findings.

#### TODO


---

#### Reminder

- NBS can potentially expand more than 2VC states, as the bound is only given for layers below f=C\*. And differently to A\*, we expand by tie-breaking on g-value and not h-value. This is due to the fact that we do not necessarily find solutions at a low h-value, meaning the frontier can be at the middle, thus h is not informative. 
- We discussed the pathological case where the f-values of backward search are much larger than the f-values of the forward search. This leads to a mixing of different f-values in the ready list, which are then sorted only considering their g-value. But the f-value cannot go over C\*, therefore the pathological case is not a problem for the last layer, as we have never f-values higher than C\* in the ready list.
- The first difference between planning and search using NBS was encountered when creating the goal set. The states within this set may not be reachable from the initial state, which is problematic as most probable those are the states with low h-value, thus, we expand illegal states before we concern ourselves with the real states. This is an immense problem as it results in a sub-optimal A\* search and occurs nearly in every domain.
    - This could be solved by using (A) a manually set single goal state, or (B) mutexes to remove all "illegal" or non-sense states. Despite there being automated mutexes, we might have to use a forward reachability analysis to check whether some states are illegal. A side possibility would be to remove non-sense backward actions.
- A possible problem and point of improvement is the flushing from the waiting to the ready list. We only hold one clb-value, therefore we mix up different f-values. It is not trivial recognizable if this is correct behaviour or needs to be adressed. 
- We discussed tie-breaking in the second open list. All states in the second open list have f-value smaller than C\*, thus, all of them _could_ be goal-paths and we only need to find one path where g + g is equal to C\*. And actually, tie breaking on h-value may provide some information, depending on the heuristic accuracy. 
- We suspected that there could be a problem when creating recursively backward actions, as those can be illegal. However, we dismiss this as we can map all backward actions to forward actions, thus as applying forward actions cannot lead to illegal states, we can only create dead ends with illegal backward actions.
- NBS Theory: We have a bound that NBS only expands twice the number of states than A\*, but only for states with f < C\*. We have no bound for expanded states in the f = C\* layer. Further, this bound only holds with consistent heuristic.
- When should NBS outperform A\*: Bidirectional blind search mostly outperforms directional blind search, thus when we have a weak heuristic, we have a similar performace to this case. Branching influence? Number of states bigger than C\*/2. (TODO more precisely)
- Why is the necesssary expansion of states in A\* equal to the one in bidirectional search? Well the point is, it isn't. However, the minimal number of expansions is given by fmm(p\*), which is equal to VC. Now, A\* must expand more than that, and NBS in the worst case twice as much. Thus, NBS does not expand more than twice than A\*. Furthermore, this also holds with the blind heuristic.
- The problems with symmetries: Remember the problem with the two walkers that could be in three different places. Only walker 1 needed to be at a specific place. We used pdb[walker1] as the heuristic. The backward search had to expand 3 symmetrical paths which were only distinguishable in the last state, as their g and h values were idendical beforehand. Showing how in the worst case, all backward initial goals are valid, indistinguishable and equally a pain in the ass. 
- About the correctness of the heuristic: The heuristic seem to be correctly computed by the backward search. 1: The task contains the goal and initial, therefore it would not compute the backward heuristic in any way. But it does. 2: It works on directed tasks where there would be no possiblity to get back. 
- There are different problems with my experiments. We have to distinguish between accidental and inherent complexity. Like, having multiple actions instead of one, altough only one is applicable in any case, may be accidental complexity stemming from the problem description.
- A question that arose was, is it really efficient to use bidirectional search. Aren't the problem in which bidirectional search outperforms unidirectional forward search just more suited to unidirectional backward search?  
- Theory to CALCULATE\_WVC: The basic idea is that Chen et al. showed that from G<sub>MX</sub> we can compute VC which is the minimal number of sufficient nodes. To feasible compute this, we we compute an abstraction of G<sub>MX</sub>, G<sub>Head</sub>. Computing the weighted VC from G<sub>Head</sub> is shown to be equal to VC of G<sub>MX</sub>. With this detour we can compute VC. The algorithm works the following.
    - Run A\* and reverse A\* to build G<sub>Head</sub>. We need the number of states per node.
        - We include all states with lb(u,v) < C\* and group them by their g-value. 
    - Compute all possible WVC from G<sub>Head</sub>. Choose the minimal as minimal WVC.  
    - -> This algorithms works thanks to the theory presented by the fmm paper. They show that all nodes of G<sub>F</sub> that are smaller than i are included without a gap. The same with j. And they introduce the dual function, computing j from i.  
- Optimal algorithm fMM: optimal p = i / C\*.  
- Adding more information, like in the case of driverlog, can actually reduce the performance of an algorithm. Driverlog:p02, is solved with less expansions when all 4 initial goals are present. There is no real downside, as three of those are dead ends. Furthermore, giving the information that at the end the trucks must be empty, changes the heuristic, in a way that it now wants to prevent loading in the first place.

#### Tools


---

#### Experiment Evaluations

- **NBS in Planning**
    - We run the NBS algorithm on all suited domains without any modification. We figured out that NBS need significantly more expansions than A\*. The main problem was that we created illegal goal for the backward search to expand. This leads the backward search on a wrong trail, whilst we exexecute a sub-optimal forward A\* search. 
    - A solution to this problem is to either give a determined goal or prune illegal states.
- **NBS with a set goal state**
    - We run NBS against A\* on problems where we set the goal as an explicit state. This improved the performance significantly and lead to useful node expansions in backward direction.
    - Next on we try to use mutexes to automize this process. Moreover, quasi illegal actions could lead to a broadened backward search.
- **NBS all statistics** (Improved)  
We run the NBS algorithm on all suited domains with verbose settings. Most important to consider are the following attributes:
    - Number of Forward Actions vs Backward Actions
        - There are nearly always a significant increase in actions in the backward search. However, this could be accounted by the actions specified for reaching all possible goals. 
        - Next Step: Count backward actions without considering the ones for the goal.
        - Follow Up: The intuition was correct, without the extra actions to the goal, we have half of the time not additional actions and the other half only a few or at least not more than twice.
    - Branching Ratio
        - Only two domains have a branching ratio >1, meaning that the backward search branches slower than the forward: \"transport-opt14-strips\" and \"trucks-strips\".
        - Next Step: Remove the initial branching from the count. As it always amplifies the backward number.
        - Follow Up: Without considering the initial branching, we have many domains with a smaller backward branching than forward. However, this branching does not definitly say something, as some domains only expand goals.
    - Expansions before Meeting
        - Most of the time we find the solution whilst being in the last layer. But not always.
    - Foward vs Backward Expansions
        - Excluding \"Elevator-opt11\", we expand the same amount of states forward as backward.
    - Number of initial goals created from the artificial one
        - Important for us are the domains where we expanded more states than there where fake goals.
        - Domains: \"Gripper\", \"Miconic\", \"Movie\", \"Pegsol-opt11-strips\", \"Scanalyzer-opt11-strips\". For all other domains we have to reduce the amount of fake goals generated before we can do anything else.
    - Pruning
        - Is always useful, but rarely enough. 
        - Next step: Prune not only states but actions.
        - Follow up: No resulting change, as it doesn't change functionality.
    - Frontier Meetings
        - Except for gripper, where we have 3 meeting points, we have only 1 meeting point.
    - Exceptions
        - 19 out-of-memory and 5 out-of-time
        - After pruning actions instead of only states: 13 out-of-memory and 11 out-of-time
    - Fazit:
        - Remove initial branching from all-time-branching to check if we have more domains with suited branching. 
        - Make new experiments where we take an in-depth look at optimised domains:
            - Use search domains. Use the ones with >1 branching ratio and set a given goal. Use some domains with not many fake goals. 
        - Fix Meeting Point.
        - Add larger problems for simple domains.
    - Fazit 2:
        - Change experiments for an in-depth look at promising domains.
            - Check meeting point. Check branching ratio >1 and set one goal.
            - Update experiments. Remove no-pruning. Add more problems per domain. etc. 
- **NBS all statistics and blind**  
All domains with four algorithms: A\*(blind), A\*(lmcut), NBS(blind), NBS(lmcut).
    - Branching Ratio
        - No notable correlation between branching ratio and competitiveness between both blind algorithms.
    - NBS(blind)
        - Never outperforms A\*(lmcut), once expands less nodes than NBS(lmcut), often expands less than A\*(blind).
        - Has more frontier meetings than NBS(lmcut).
        - transport-opt14-strips, probably prime example why bidirectional search can outperform directional, at least blind.
        - NBS(blind) often outperform A\*(blind) when the number of initial goals is low. Leading to the assumption that it could outperform A\*(blind) even more consistently when there is only a single goal.
- **Full domain**
    - Problems were NBS(lmcut) outperformed A\*(lmcut): driverlog:p02.pddl, ged-opt13-strips:{d-2-3.pddl,d-3-2.pddl}, gripper:prob03.pddl, pegsol-opt11-strips:p11.pddl, psr-small:{5x}, scanalyzer-opt11-strips:{p02.pddl,p11.pddl}.
    - Further, NBS(blind) outperforms A\*(blind) regularly.
    - Special: NBS(lmcut) better than NBS(blind) > A\*(lmcut) > A\*(blind) at pegsol-opt11-strips:p11.pddl and gripper:p03.pddl, however, only expansions wise.
- **Single Goal**
    - NBS(blind) is significantly improved. However, NBS(lmcut) is mostly proportionally improved like A\*(lmcut).
    - NBS(lmcut) outperforms A\*(blind) on the following problems:
        - driverlog:{p02,p04}, ged-opt14-strips:{2-3, 3-2}, gripper:p03
    - The experiments suggest a causality between performance and the quality of the forward and respectively backward heuristic.
- **Single Goal - Expansions before Jump**
    - We want to confirm our theoretical bound.
    - The tested domains confirm our theory.
    - Follow Up: Having confirmed our bounds, we want to test the influence of heuristic on the performance. 
- **Full domain - New Statistics**
    - These are nearly the same experiments as before, except that we have more statistics.
    - Notable findings:
        - ged-opt14-strips: some problems that are not improved by reducing goal. Giving the impression that the heuristic prevents them from expanding them. Maybe a best case example?
        - ged-opt14-strips: the first problem have a very bad performance with NBS. Maybe a worst case example?
        - movie: can be kicked out, no variation.
        - psr-small: very promising domain for tests. Add psr-medium and psr-big.
        - satellite, trucks-strips: might perform decent with single goal.
        - scanalyzer-opt11-strips: interesting domain, already single goal. displays great and miserable performance. Might give insight when analyzing which are bad and which good.
        - storage, tpp: extreme initial goals, but decent even though worse performance. Again positive example of many initial goals are ignored.
        - transport-opt14-strips, zenotravel: good performance of bi-bs even though we have many initial goals. Might be due to pruning.
        - Heuristics: There seems to be a correlation between whether forward/backward heuristic is superior, and whether NBS is superior to A\*.
- **Heuristics - Driverlog**
    - Prerequisite
        - A detailed experiment about the driverlog domain solved by different algorithms.
        - Algorithms: A\* + NBS | blind + hmax + lmcut + hm | Modified + Original Domain
    - Results
        - NBS(hmax) consistently outperforms the A\* variant. Except in domains where the initial branching is critical. 
        - How balanced the forward and backward heuristic is seems to depend on the problem.
        - Heuristic strengts: lmcut > hm > max > blind. 
        - Two main criteria: Ratio between backward and forward heuristic. Heuristic strength. We want the backward heuristic to be better than backward, and we want forward to be as low as possible.
- **Optimal Domain**
    - *Unsuited domains*: agricola-opt14-strips, airport\*, barman-optXX-strips, 
    childsnack-opt14-strips, data-network-opt18-strips\*, elevators-optXX-strips, 
    floortile-opt14-strips, freecell, grid, logistics98, movie, mprime\*, mystery,
    openstacks-opt1X-strips, organic-synthesis-X-opt18-strips, parcprinter-optXX-strips,
    parking-optXX-strips, pathways-noneg, petri-net-alignment-opt18-strips,
    pipesworld-[no]tankage, snake-opt18-strips, sokoban-optXX-strips, 
    spider-opt18-strips, tetris-opt14-strips, tidybot-optXX-strips, 
    visitall-opt14-strips, woodworking-optXX-strips
    - *NBS outperforms A*\*: blocks, depot, driverlog, floortile-opt11-strips, 
    ged-opt14-strips, gripper, logistics00, miconic, nomystery-opt11-strips, 
    openstacks-opt08-strips, openstacks-strips, pegsol-XX-strips, psr-small, 
    scanalyzer-08-strips, termes-opt18-strips, 
    - *NBS works, but not that good*: hiking-opt14-strips, rovers, satellite, 
    storage, tpp, transport-optXX-strips, trucks-strips, visitall-opt11-strips,
    zenotravel
- **14 - Full domain - New Report**
    - Description: We run A\* and NBS over all domains where at least a few problems were solvable with NBS. We run both algorithm with each heuristic: Blind, Max, HM, LMCut.
    - Remarks
        - Blind
            - Except like 4 problems, NBS did always expand at most two times the number of states than A\*.
            - NBS often expands less states than A\*, unless there is a high initial branching.
            - A\* is able to solve significantly more problems than NBS. I expect the biggest performance loss is due to the frontier detection. Which should be easily fixed.  

        - Max
            - Similar to Blind, NBS often expands less than A\*. However, it shifted slightly. Some problems were performing bad with Blind, but with Max they are decent, because many initial goals are getting ignored. On the other hand, problems which performed good, are now worse than A\*, because the heuristic guides A\* so much more efficient.
            - Except like 4 problems, NBS did always expand at most two time the number of states than A\*. Same as with blind.
            - A correlation between heuristic quality and performance is clearly visible.
        - LMCut and HM
            - Usual behaviour.
        - Blocks
            - Very suited domain, as the backward branching is backward smaller. Due to the fact that we only have one clear block on top of the single tower. It is basically a search domain, thus, no extra actions and such. The initial goals are neglectable as they are all dead ends, due to them being illegal. NBS solves block problems better unless we apply a very accurate heuristic, which improves A\* too much. 
        - Depot
            - This domain has a large number of initial goals, turning bidirectional blind search into a forward blind search, where we expand double the number of states. However, with even a bad heuristic like max, we can recognize all other initial goals as unnecessary and outperform A\*. But only with max heuristic, as soon as the heuristics are more improved, A\* has back its advantage. 
        - Driverlog
            - A seemingly promising domain, however, we have an essential complexity due to a number of legal initial goal states. These lead to promising expansions, parallel to the real solution path, however at the end they need expensive actions to reach the initial state. Moreover, there is an accidental complexity due to ambigous action definitions.
        - Domains where NBS never outperforms A\*
            - Those domains have usually a high number of initial goals throughout the domain. They may be interesting to analyze with only one initial goal.
            - elevators-opt11-strips (which performs much better), hiking-opt14-strips (which is improved greatly, yet only closely outperforms A\*, and only with blind.) 
- **15 - Single Goal Domain - New Report**
    - Not much to say here.
- **16 - Full Domain - New Report and Optimization**
    - _Modifications:_ The new reports, reduced frontier detection complexity to O(1), and disabled pruning. 
    - _Seeked Answers:_ 
        - Are the expansions in the last layer relevant? 
        - With the optimizations, can we solve problems A\* is not able to?
    - _All Domains:_
        - [++] Blocks: Very good. Outperforms A\* clearly.
        - [+-] Depot: Blind is abyssimal due to high initial goals. Performance improves with heuristic, altough it wastes a lot of time with those.
        - [+-] Driverlog: Not optimal, especially lmcut is worse with NBS. A lot of expanded states seem to occur in the last layer.
        - [+-] Elevators-optXX-strips: Decent performance, even though initial goals hurt a lot.
        - [++] Floortile-optXX-strips: Outperforms A\* everywhere.
        - [++] Ged-opt14-strips: Weird domain, but over all very good.
        - [++] Gripper: Mostly good. But weird parallelism between heuristics.
        - [+-] Hiking-opt14-strips: Okay, but seems to have problems with initial goals.
        - [++] Logistics00: Pretty good. But Lmcut seems to add much more information in A\*.
        - [+-] Maintenance-opt14-strips: Okay, Initial goal seem to be problematic.
        - [+-] Miconic: Okay. Worse with good heuristic.
        - [++] Nomystery-opt11-strips: Pretty good, again lmcut is worst.
        - [+-] Openstacks-optXX-strips: Blind is bad because of initial goals. But lmcut seems to be okay thanks to the guidance.
        - [++] Pegsol-optXX-strips: Great domain.
        - [+-] Petri-net-opt18-strips: Weirdly bad. Should be better. Maybe the number of new actions is the problem.
        - [+-] Psr-small: Good, but high number of initial goals. Heuristics help though.
        - [--] Rovers: Not too good, many initial goals, and many expansions in last layer.
        - [--] Satellite: Same old problem.
        - [++] Scanalyzer-optXx-strips: Very good, only one initial goal.
        - [--] Storage: Way to many initial goals. 
        - [++] Termes-opt18-strips: NBS outperforms A\* on every problem. Even though there exist a few initial goals.
        - [--] Tpp: Too many initial goals, and many expansions after last jump.
        - [+-] Transport-optXX-strips: Too many initial goals.
        - [+-] Trucks-strips: Too many initial goals.
        - [+-] Visitall-optXX-strips: Decent good.
        - [+-] Zenotravel: Okay, but not great.
    - _Remarks:_
        - There seems to be a correlation between good heuristics and expanding most states in the last layer.
- **25+26 - Full Domain - fMM + computeWVC**
    - _Remarks:_
        - Which direction is more efficient for a problem is mostly unchanged over each domain. Giving the opportunity to forecast which algorithm should be used for unsolved problems.
        - Check if the domains with F >> B have many initial goals.
    - _All Domains:_
        - *[++]* Blocks: Bi > B > F. Very good domain, shows that bidirectional can shine. Even some examples where only fmm with p close to 0.5 are solved, and not astar.
        - [+-] Depot: Clear example where p\* close to 0.5 defines good behaviour.
        - [+-] Driverlog: Shows why only a few problems are efficient with NBS.
        - [+-] Elevators-optXX-strips: Consistently better for forward search.
        - [++] Floortile-optXX-strips: Consistently better for backward search.
        - [++] Ged-opt14-strips: Decent, some flat graphs. 
        - [++] Gripper: Decent, very flat graphs. Max difference being < 1.5x.
        - [+-] Hiking-opt14-strips: Consistently better for forward search. Never bidirectional.
        - *[++]* Logistics00: Very good bidirectional.
        - [+-] Maintenance-opt14-strips:
        - [+-] Miconic: Interesting behaviour, mostly better straight forward.
        - [++] Nomystery-opt11-strips: F > Bi > B
        - [+-] Openstacks-optXX-strips: (08) Really bad in anything but forward. (strips) Mostly backward, but optimum in the middle. 
        - [++] Pegsol-optXX-strips: F > Bi > B, rarely Bi > F > B
        - [+-] Petri-net-opt18-strips: 
        - [+-] Psr-small: Mostly: F > Bi > B, but rarely Bi >> F > B
        - [--] Rovers: F >> Bi > B 
        - [--] Satellite: F >> Bi > B
        - *[++]* Scanalyzer-optXx-strips: Bi >> F = B, very good domain. Very consistent.
        - [--] Storage: F >> Bi > B
        - *[++]* Termes-opt18-strips: Bi > F >> B
        - [--] Tpp: F >> Bi > B
        - [+-] Transport-optXX-strips: F >> Bi > B
        - [+-] Trucks-strips:
        - [+-] Visitall-optXX-strips:
        - [+-] Zenotravel: okey.

---

#### Domains

- **Driverlog**
    - We create 84 states from the artificial goal. 12 of those can be detected as illegal states by the automated mutexes. However, 30 more illegal states are not recognized.
    - Furthermore, because disembarking does not check whether the truck is full, we get backward actions were the truck is full or empty, thus we create illegal states. (This can easily be fixed by adding another fact to the precondition)
    - Even with the fixed actions, we do not get more mutexes, therefore, only the single goal case is efficient. 

---

#### Profiling

**Work Flow**  
1. Translator
2. Initialization
    - Bidi Constructor
        - Di Constructor 2x
    - Bidi Initialize()
        - Di Initialize() 2x
3. Running Search (Loop)
    - Prepare Expansion Candidates
    - Expand Backward / Forward
        - Check if frontiers meet
        - Generate successor states

We want to analyze where the most resources are used. But only for the parts we can influence. We focus on the search loop, as every improvement is applied for every iteration. The search contains three main resource eater: 
- Checking whether a state is a dead end. (For every generation)
    - Compute Heuristic.
- Checking whether the frontiers meet. (For every expansion)
    - getNodeAndCheck() -> getValues()
    - Reduced to O(1) complexity.
- Checking whether a state violates predefined mutexes. (For every generation)
    - getValues()
    - Disabled as it weren't doing anything except for the trucks-strips domain.


---

#### Command and Link Archive

```
ssh bufmar00@login-infai.scicore.unibas.ch
scp bufmar00@login-infai.scicore.unibas.ch:~/[extern_path_to_file] [local_path_to_file]

hg tag -r tip "[tag_name]"
hg branch [branch_name]
hg push --new-branch
hg update [branch_name]

./fast-downward.py --translate PROBLEM.PDDL
valgrind --tool=callgrind --callgrind-out-file=callgrind.out \
    --dump-instr=yes --collect-jumps=yes \
    ./builds/release64/bin/downward --search "astar(blind())" < output.sas
kcachegrind callgrind.out

squeue -o "%22i %9P %40j %10u %2t %.10M %.6D %16R %8Q" | tac
https://bitbucket.org/aibasel/scripts
https://bitbucket.org/malte/autonice
killall python
nohup ./autonice.py --log-file ~/autonice-infai_1.log infai_1 &
nohup ./autonice.py --log-file ~/autonice-infai_2.log infai_2 &

:%s/\\multicolumn{1}{|l|}{\([0-9|None]*\)}/\1/g
:%s/\\multicolumn{1}{|l|}{\([0-9|\\textbf|{|}]*\)}/\1/g
:%s/None/0/g
```
