it work.
\subsection{Assignment 1-2}
-Assignment 2 took us a week, it was much more difficult our knowledge of prolog
+Assignment 2 took us a week, it was much more difficult, but our knowledge of prolog
was increased significantly so we weren't stopped by trivial prolog problems and
-could work on it much more efficiently.
+could work on it much more efficiently. On the other hand, the algorithm is in its
+difficulty programming a very steep climb in prolog programming and we
+would definitly recommend splitting this assignment up more.
\subsection{General remarks}
-In our opinion the amount of information provided about the hittingset
-algorithm and situation calculus is out of proportion concidering the very
+In our opinion the amount of information provided about the hitting-set
+algorithm and situation calculus is out of proportion considering the very
important part it plays. For example situation calculus barely gets one page in
-the reader and hitting set is also very sparsely described.
+the reader and hitting set is also very sparsely described. We would really like
+to have more clear information about each part of this algorithm. Some details,
+such as the tp function, took hours of staring at code to finally understand it.
\subsection{Implementation of the hitting-set algorithm}
\subsubsection{Task 12: Generate conflict}
Can be found in \textit{./src/task12.pl} or in Listing~\ref{task12}.
+\\ \\The tp command runs through a list of commands, which we will discuss here in the same order:
+\\Subtract: removes the components assumed to be abnormal from the set of all components and puts these in NormComp (the predicates assumed to be normal.).
+\\Maplist: maps the function Normal over all pairs of NormComp (the predicates assumed to be normal) into S, letting S be NormComp, but with all predicates X becoming ~ab(X).
+\\Append3: appends SD (list of first-order formula), S (normal predicates) and OBS (the observed (ground) facts) into Theory (that which is actually going to be tested, SD ∪ OBS ∪ {¬Ab(c) | c ∈ CS}, needed to be proven inconsistent if CS is going to be a valid conflict set).
+\\Conjunction: turns every element of Theory into conjunctions. These conjunctions are F (the formula that needs to be tested for inconsistency).
+\\Ground: constructs the ground formula that needs to be proven if it’s inconsistent. It establishes all logical symbols in the new formula F2 using all the logic rules in order and instantiates the existential and global variables using COMP (the set of all components).
+\\Break: stopping the prolog stack here so no backtracking will be done.
+\\Prove/1: Tries to establish the truth of the negated F2 formula and keeps backtracking until some solution is found.
+\\Prove/2: Finds the proof established in the statement above and puts the proof into Proof.
+\\Flatten: Breaks down the structure of the proof into its elements into FlatProof.
+\\Include: filters the abnormal elements from the FlatProof and puts them into Abs.
+\\Maplist: removes the ab() predicate from each component and puts them into CompProof.
+\\List-to-set: turns CompProof into CompSorted by turning the list(CompProof) into a set (CompSorted) that is sorted (which is not necessary) but which does not contain any duplicate elements.
+\\Subtract: removes any elements that were already considered abnormal from CompSorted and puts them in the final result of the function: CS.
+\\Break: another break to prevent prolog from backtracking after a result has been found.
+\\ \\In conclusion, tp determines the conflict set for a certain system with certain observations done on it and with certain assumptions on parts of the system.
+\newpage
\subsubsection{Task 13: Define your data structure}
-Can be found in \textit{./src/hs.pl} or in Listing~\ref{hs}.
+We use the nodes and leaves for our data structure. A node contains two lists. The first one contains a list of edge labels. The second one contains a list of new nodes or leaves. Both lists in the node predicate need to have the same size, since each edge label corresponds to a branch.
+\\ \\Good examples:
+\\Tree 1: node([a,b,],[leaf,leaf]).
+\\Tree 2: node([a,b],[node([c,d],[leaf,leaf]),leaf]).
+\\Wrong examples:
+\\Tree 3: node([a,b],[node([c,a],[leaf,leaf]),leaf]).
+\\Tree 4: node([a,b,c],[node([b,c],[leaf,leaf]),leaf]).
+\\ \\Tree 3 has a duplicate edge label in a path from root to leaf and thus is an incorrect hitting-set tree. Tree 4 is missing an entire branch for the edge label in the root.
+\\ \\Our isHittingSetTree(Tree) can be found in \textit{./src/hs.pl} or in Listing~\ref{hs}.
\begin{figure}[H]
- \caption{Examples of good hitting set trees}
+ \caption{Tree 1 and Tree 2}
\begin{tikzpicture} [grow=down]
\node[bag] {\{$a, b\}$}
child {
\end{figure}
\begin{figure}[H]
- \caption{Examples of bad hitting set trees due to duplicate edge labels}
+ \caption{Tree 3 and Tree 4}
\begin{tikzpicture} [grow=down]
\node[bag] {\{$a, b\}$}
child {
node[right] {$b$}
};
\end{tikzpicture}
+\begin{tikzpicture} [grow=down]
+ \node[bag] {\{$a, b,c\}$}
+ child {
+ node[bag] {$\{b, c\}$}
+ child {
+ node[end, label=below:$\checkmark$]{}
+ edge from parent
+ node[left] {$b$}
+ }
+ child {
+ node[end, label=below:$\checkmark$]{}
+ edge from parent
+ node[left] {$c$}
+ }
+ edge from parent
+ node[left] {$a$}
+ }
+ child {
+ node[end, label=below:$\checkmark$]{}
+ edge from parent
+ node[right] {$b$}
+ };
+ \end{tikzpicture}
\end{figure}
+\newpage
\subsubsection{Task 14: Implementation}
-Can be found in \textit{./src/task14part1.pl} or in Listing~\ref{task14part1}.
-Can be found in \textit{./src/task14part2.pl} or in Listing~\ref{task14part2}.
+How we generate hitting-set trees can be found in \textit{./src/task14part1.pl} or in Listing~\ref{task14part1}.
+\\How we extract diagnoses and get the subset minimal diagnoses can be found in \textit{./src/task14part2.pl} or in Listing~\ref{task14part2}.
+\\Problem 1:
+\\Hitting-set tree = node([a1], [node([a2], [leaf])]),
+\\Diagnoses = [[a1, a2]]
+\\Smallest Diagnoses = [[a1, a2]]
+\\ \\Problem 2:
+\\HS = node([a1, a2], [leaf, leaf]),
+\\DIAG = [[a1], [a2]]
+\\MIN = [[a1], [a2]]
+\\ \\Problem 3:
+\\HS = node([a1, o1, a2], [node([a2, o1], [leaf, leaf]), leaf, node([a1, o1], [leaf, leaf])]),
+\\DIAG = [[a1, a2], [a1, o1], [o1], [a2, a1], [a2, o1]],
+\\MIN = [[o1]]
+\\ \\Fulladder:
+\\HS = node([a1, x1, a2, r1, x2], [node([a2, x2, x1], [node([x1, x2], [leaf, leaf]), node([a2, r1, x1], [leaf, leaf, leaf]), leaf]), leaf, node([a1, x1, x2], [node([x1, x2], [leaf, leaf]), leaf, leaf]), node([a1, x1, a2|...], [node([a2|...], [node(..., ...)|...]), leaf, node(..., ...)|...]), node([a1, x1|...], [node([...|...], [...|...]), leaf|...])]),
+\\DIAG = [[a1, a2, x1], [a1, a2, x2], [a1, x2, a2], [a1, x2, r1], [a1, x2, x1], [a1, x1], [x1], [a2|...], [...|...]|...],
+\\MIN = [[x1]]
+\\ \\We had problems implementing how we can get subset-minimal subsets from all possible diagnoses, so we just tried to find the smallest diagnoses as another challenge. All our results are correct, since they correspond to our calculations done by hand or to the answers on the slides. A big problem we had was how to generate conflict set using tp. With some help of the internet, we found the prolog if-then-else construction, which is nice, but doesn't feel like real logic programming. Thus this is a point where improvement is possible (be it maybe not an optimalization). We think we lost track of the getting subset-minimal subsets when we first made the function that extracts all possible diagnoses, maybe we had to get those while running through the hitting set tree. Our code looks very efficient on the outside, at least to us, but when we were tracing calls we found alot of repetitions sometimes, so maybe break statements to reduce backtracking would be a nice improvement in some places. And of course, other improvements for, for example pruning the hitting-set tree, can be implemented.
\ No newline at end of file
-isHittingSetTree(_, leaf).
-isHittingSetTree(_, node([], [])).
-isHittingSetTree(VisitedLabels, node([CurLabel|Labels], [CurChild|Children])) :-
- not(member(CurLabel, VisitedLabels)),
- append(VisitedLabels, [CurChild], UpdatedVisitedLabels),
- isHSTree(UpdatedVisitedLabels, CurChild),
- isHSTree(VisitedLabels, node(Labels, Children)).
+:- [diagnosis].\r
+%Function to add variable for uniqueness checking.\r
+isHittingSetTree(Tree) :-\r
+ isHittingSetTree2(Tree, []). \r
+\r
+%When the end of branch has been reached.\r
+isHittingSetTree2(leaf, _). \r
+%When a node turns empty. \r
+isHittingSetTree2(node([], []), _). \r
+%When a node isn't empty.\r
+isHittingSetTree2(node([CurLabel|Labels], [CurChild|Children]), VisitedLabels) :-\r
+ %Check if label has already been used up in the tree.\r
+ not(member(CurLabel,VisitedLabels)),\r
+ %Append label to list of checked labels\r
+ append(VisitedLabels, [CurLabel], UpdatedVisitedLabels), \r
+ %Recursively search into depth of branch.\r
+ isHittingSetTree2(CurChild, Appended), \r
+ %Recursively search into width of node.\r
+ isHittingSetTree2(node(Labels, UpdatedVisitedLabels), VisitedLabels).\r
+%If there are more or less labels then children, the tree will not match and \r
+%the function will rightfully report false.\r
:- [diagnosis].\r
\r
-%test with problem1(SD,COMP,OBS),\r
+%Test with problem1(SD,COMP,OBS),\r
%generateHittingSetTree(SD,COMP,OBS,[],HSTREE). This needs to report node([a1],\r
%[node([a2], [leaf])]).\r
-%second part of the OR is needed to translate an empty conflict set into a leaf. \r
+%Second part of the OR is needed to translate an empty conflict set into a leaf. \r
generateHittingSetTree(SD, COMP, OBS, HS, HSTREE) :-\r
+ %Prolog version of: if -> then ; else, here used to generate conflict sets.\r
tp(SD, COMP, OBS, HS, CS) -> generateParts(SD, COMP, OBS, HS, CS, HSTREE);\r
generateParts(_,_,_,_, [], HSTREE). \r
\r
-%generates leaf if at the end of all possible conflict sets in a branch\r
+%Generates leaf if at the end of all possible conflict sets in a branch\r
generateParts(_,_,_,_, [],leaf).\r
-%generates node if the conflict set isn't empty and goes on.\r
+%Generates node if the conflict set isn't empty and goes on.\r
generateParts(SD, COMP, OBS, HS, CS, node(CS, RESTOFTREE)) :- \r
- %repairs the branch by branching out for each item in the conflict set and\r
+ %Repairs the branch by branching out for each item in the conflict set and\r
%generating new conflict sets for the next node\r
repairBranch(SD, COMP, OBS, HS, CS, RESTOFTREE). \r
\r
-%single item left in conflict set\r
+%Single item left in conflict set:\r
repairBranch(SD, COMP, OBS, HS, [CONFLICTITEM], [BRANCH]) :- \r
- %add the used conflict set item for this branch to the new hitting set\r
+ %Add the used conflict set item for this branch to the new hitting set\r
append(HS, [CONFLICTITEM], HSNEW),\r
- %find the next new conflict set with the new hitted item\r
+ %Find the next new conflict set with the new hitted item added builds next tree-part.\r
generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCH).\r
-%multiple items left in conflict set\r
+%Multiple items left in conflict set:\r
repairBranch(SD, COMP, OBS, HS, [CSHEAD|CSTAIL], [BRANCHHEAD|BRANCHTAIL]) :-\r
- %add the used conflict set item for this branch to the new hitting set\r
+ %Add the used conflict set item for this branch to the new hitting set.\r
append(HS, [CSHEAD], HSNEW),\r
- %find the next new conflict set with the new hitted item\r
+ %Find the next new conflict set with the new hitted item added and builds next tree-part.\r
generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCHHEAD),\r
- %goes on in recursion for each item in the conflict set of the current node\r
+ %Goes on in recursion for each item in the conflict set of the current node (the width of the branch).\r
repairBranch(SD, COMP, OBS, HS, CSTAIL, BRANCHTAIL).\r
:- [task14part1].\r
\r
-% Adding a variable for the current path\r
+% Adding a variable for the current path.\r
extractDiagnoses(HSTree,Diagnoses):-\r
extractDiagnoses2(HSTree, Diagnoses, []). \r
\r
% Calls length single diagnosis\r
length(Diagnosis,DiagnosisLength). \r
getLengthSmallestSet([HeadDiagnosis|RestOfDiagnoses], Minimal):-\r
- % Recursively gets the length of tail\r
+ % Recursively gets the length of tail.\r
getLengthSmallestSet(RestOfDiagnoses, RestLength),\r
- % Initialises length of the head diagnosis\r
+ % Initialises length of the head diagnosis.\r
length(HeadDiagnosis,HeadLength),\r
- % Gets minimal length of diagnoses\r
+ % Gets minimal length of diagnoses.\r
Minimal is min(HeadLength, RestLength).\r
\r
filterLength(X,Y):-\r
length(Y, LengthY),\r
- %checks if the set isn't bigger than the checked set\r
+ %Checks if the set isn't bigger than the smallest set.\r
X \== LengthY. \r
\r
-% Deze functie moet opnieuw geschreven worden, hij moet de subsetminimal\r
-% opleveren en niet de kleinste diagnoses\r
+\r
getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets):- \r
+ %Gets the length of the smallest set to prune the diagnoses. \r
+ %Break so that there will be no backtracking if something goes wrong.\r
getLengthSmallestSet(DiagnosesSets,Length),!,\r
% Excludes sets that are bigger than the smallest set\r
exclude(filterLength(Length), DiagnosesSets, MinimalDiagnosesSets).\r
\r
-% Function that returns minimal hitting sets from a problem\r
-subsetMinimalDiagnoses(SD, COMP, OBS, MinimalDiagnosesSets) :-\r
- % Generate hitting tree\r
+% Function that returns minimal hitting sets from a problem.\r
+subsetMinimalDiagnoses(SD, COMP, OBS, HsTree, DiagnosesSets, MinimalDiagnosesSets) :-\r
+ % Generate hitting tree.\r
generateHittingSetTree(SD, COMP, OBS, [], HsTree),\r
write(HsTree),\r
- % Get diagnoses out of the hitting tree\r
+ % Get diagnoses out of the hitting tree.\r
extractDiagnoses(HsTree, DiagnosesSets),\r
write(DiagnosesSets),\r
- % Determine subset minimal diagnoses\r
+ % Determine smallest diagnoses.\r
getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets).\r
repositories / ker1415-1.git / commitdiff