Passed
Push — master ( 00d193...bc2940 )
by Alessandro
08:14
created

expand(SearchSpaceNode,Flaw)   B

Complexity

Conditions 5

Size

Total Lines 49
Code Lines 21

Duplication

Lines 0
Ratio 0 %

Importance

Changes 0
Metric Value
cc 5
eloc 21
dl 0
loc 49
rs 8.9093
c 0
b 0
f 0
1
package it.cnr.istc.pst.platinum.ai.deliberative.solver;
2
3
import java.util.ArrayList;
4
import java.util.Collections;
5
import java.util.List;
6
7
import it.cnr.istc.pst.platinum.ai.deliberative.heuristic.FlawSelectionHeuristic;
8
import it.cnr.istc.pst.platinum.ai.deliberative.strategy.SearchStrategy;
9
import it.cnr.istc.pst.platinum.ai.framework.domain.component.PlanDataBase;
10
import it.cnr.istc.pst.platinum.ai.framework.microkernel.FrameworkObject;
11
import it.cnr.istc.pst.platinum.ai.framework.microkernel.annotation.inject.deliberative.FlawSelectionHeuristicPlaceholder;
12
import it.cnr.istc.pst.platinum.ai.framework.microkernel.annotation.inject.deliberative.SearchStrategyPlaceholder;
13
import it.cnr.istc.pst.platinum.ai.framework.microkernel.annotation.inject.framework.PlanDataBasePlaceholder;
14
import it.cnr.istc.pst.platinum.ai.framework.microkernel.annotation.lifecycle.PostConstruct;
15
import it.cnr.istc.pst.platinum.ai.framework.microkernel.lang.ex.NoSolutionFoundException;
16
import it.cnr.istc.pst.platinum.ai.framework.microkernel.lang.ex.OperatorPropagationException;
17
import it.cnr.istc.pst.platinum.ai.framework.microkernel.lang.ex.PlanRefinementException;
18
import it.cnr.istc.pst.platinum.ai.framework.microkernel.lang.flaw.Flaw;
19
import it.cnr.istc.pst.platinum.ai.framework.microkernel.lang.flaw.FlawSolution;
20
import it.cnr.istc.pst.platinum.ai.framework.microkernel.lang.plan.Plan;
21
import it.cnr.istc.pst.platinum.ai.framework.microkernel.resolver.ex.UnsolvableFlawException;
22
23
/**
24
 * 
25
 * @author anacleto
26
 *
27
 */
28
public abstract class Solver extends FrameworkObject {
29
	
30
	@PlanDataBasePlaceholder
31
	protected PlanDataBase pdb;
32
	
33
	@SearchStrategyPlaceholder
34
	protected SearchStrategy fringe;
35
	
36
	@FlawSelectionHeuristicPlaceholder
37
	protected FlawSelectionHeuristic heuristic;
38
	
39
	protected long timeout;
40
	protected long time;
41
	protected long stepCounter;
42
	protected String label;
43
	
44
	/**
45
	 * 
46
	 * @param label
47
	 * @param timeout
48
	 */
49
	protected Solver(String label, long timeout) {
50
		super();
51
		this.label = label;
52
		this.timeout = timeout;
53
	}
54
	
55
	/**
56
	 * 
57
	 */
58
	@PostConstruct
59
	protected void init() {
60
		
61
		// create the root node
62
		SearchSpaceNode root = new SearchSpaceNode();
63
		// set initial partial plan
64
		root.setPartialPlan(this.pdb.getPlan());
65
		// check flaws
66
		for (Flaw f : this.pdb.checkFlaws()) {
67
			root.addCheckedFlaw(f);
68
		}
69
		
70
		// enqueue the root node
71
		this.fringe.enqueue(root);
72
	}
73
	
74
	/**
75
	 * 
76
	 * @return
77
	 * @throws NoSolutionFoundException
78
	 */
79
	public abstract SearchSpaceNode solve() 
80
			throws NoSolutionFoundException;
81
82
	/**
83
	 * 
84
	 */
85
	public abstract void clear();
86
	
87
	/**
88
	 * 
89
	 * @return
90
	 */
91
	protected SearchSpaceNode createSearchSpaceNode() {
92
		return new SearchSpaceNode();
93
	}
94
	
95
	/**
96
	 * 
97
	 * @return
98
	 */
99
	public String getLabel() {
100
		return label;
101
	}
102
	
103
	/**
104
	 * 
105
	 * @param node
106
	 */
107
	protected void backtrack(SearchSpaceNode node) 
108
	{
109
		// list of operators that have been applied to generate the node
110
		List<Operator> operators = node.getOperators();
111
		// retract operators starting from the more recent ones
112
		Collections.reverse(operators);
113
		// retract all operators
114
		for (Operator operator : operators) {
115
			// retract operator
116
			this.pdb.retract(operator);
117
		}
118
	}
119
	
120
	/**
121
	 * 
122
	 * @param node
123
	 * @throws OperatorPropagationException
124
	 */
125
	protected void propagate(SearchSpaceNode node) 
126
			throws PlanRefinementException {
127
		
128
		// get the list of applied operators
129
		List<Operator> operators = node.getOperators();
130
		// list of committed operators
131
		List<Operator> committed = new ArrayList<>();
132
		try {
133
			
134
			// propagate operators in chronological order
135
			for (Operator operator : operators) {
136
				
137
				// propagate operator
138
				this.pdb.propagate(operator);
139
				// add committed operator
140
				committed.add(operator);
141
			}
142
			
143
		} catch (OperatorPropagationException ex) {
144
			
145
			// retract committed operators in reverse order
146
			Collections.reverse(committed);
147
			for (Operator operator : committed) {
148
				this.pdb.retract(operator);
149
			}
150
151
			// throw exception
152
			throw new PlanRefinementException("Error while propagating node:\n" + node + "\n- message: " + ex.getMessage() + "\n");
153
		}
154
	}
155
	
156
	/**
157
	 * 
158
	 * @param last
159
	 * @param extracted
160
	 * @throws PlanRefinementException
161
	 */
162
	protected void contextSwitch(SearchSpaceNode last, SearchSpaceNode extracted) 
163
			throws PlanRefinementException {
164
		
165
		// compare the two nodes
166
		if (last != null) {
167
			
168
			// prepare a list of operators to retract 
169
			List<Operator> toRetract = new ArrayList<>();
170
			// prepare a list of operators to propagate
171
			List<Operator> toPropagate = new ArrayList<>();
172
			
173
			// get the list of operators of the nodes
174
			List<Operator> lastNodeOperators = last.getOperators();
175
			List<Operator> extractedNodeOperators = extracted.getOperators();
176
			
177
			// check min length between the two lists
178
			int minLength = Math.min(lastNodeOperators.size(), extractedNodeOperators.size());
179
			// check potentially common operators
180
			boolean common = true;
181
			for (int i = 0; i < minLength; i++) {
182
				
183
				// check common flag
184
				if (common && !lastNodeOperators.get(i).equals(extractedNodeOperators.get(i))) {
185
					common = false;
186
				}
187
				
188
				// check if no common operators have been found
189
				if (!common) {
190
					
191
					// add operator to the different lists
192
					toRetract.add(lastNodeOperators.get(i));
193
					toPropagate.add(extractedNodeOperators.get(i));
194
				}
195
			}
196
			
197
			// check other operators to retract
198
			for (int i = minLength; i < lastNodeOperators.size(); i++) {
199
				toRetract.add(lastNodeOperators.get(i));
200
			}
201
			
202
			// check other operators to propagate
203
			for (int i = minLength; i < extractedNodeOperators.size(); i++) {
204
				toPropagate.add(extractedNodeOperators.get(i));
205
			}
206
			
207
			
208
			// retract operators in reverse order
209
			Collections.reverse(toRetract);
210
			// retract all operators
211
			for (Operator operator : toRetract) {
212
				// retract operator
213
				this.pdb.retract(operator);
214
			}
215
			
216
			// list of committed operators
217
			List<Operator> committed = new ArrayList<>();
218
			
219
			try {
220
				
221
				// propagate operators in chronological order
222
				for (Operator operator : toPropagate) {
223
					
224
					// propagate operator
225
					this.pdb.propagate(operator);
226
					// add committed operator
227
					committed.add(operator);
228
				}
229
				
230
			} catch (OperatorPropagationException  ex) {
231
				
232
				// retract committed operators in reverse order
233
				Collections.reverse(committed);
234
				for (Operator operator : committed) {
235
					// retract operator
236
					this.pdb.retract(operator);
237
				}
238
				
239
				// also restore retracted operators
240
				Collections.reverse(toRetract);
241
				for (Operator operator : toRetract) {
242
					
243
					try {
244
					
245
						// restore operator
246
						this.pdb.propagate(operator);
247
						
248
					} catch (OperatorPropagationException exx) {
249
						warning("[ContextSwitch] Error while restoring operators after failure:\n"
250
								+ "- message: " + ex.getMessage() + "\n");
251
					}
252
				}
253
254
				// throw exception
255
				throw new PlanRefinementException("Error while propagating node:\n" + extracted + "\n- message: " + ex.getMessage() + "\n");
256
			}
257
			
258
		} else {
259
			
260
			// simply propagate extracted node
261
			this.propagate(extracted);
262
		}
263
	}
264
	
265
	/**
266
	 * 
267
	 * Expand the search space by adding a new node for each solution of the flaw selected for 
268
	 * plan refinement
269
	 * 
270
	 * @param current
271
	 * @param flaw
272
	 * @return
273
	 * @throws UnsolvableFlawException
274
	 */
275
	protected List<SearchSpaceNode> expand(SearchSpaceNode current, Flaw flaw) 
276
			throws UnsolvableFlawException {
277
		
278
		// list of child nodes
279
		List<SearchSpaceNode> list = new ArrayList<>();
280
		// check if no expansion has done
281
		if (flaw.getSolutions().isEmpty()) {
282
			// this is for debug mainly, as this condition should never occur. Computed flaw solutions should be valid 
283
			throw new UnsolvableFlawException("Search space expansion failure as no valid operator can be applied:\n"
284
					+ "- current node: " + current + "\n"
285
					+ "- flaw: " + flaw + "\n");
286
		}
287
				
288
		// check flaw solutions
289
		for (FlawSolution solution : flaw.getSolutions()) {
290
			
291
			// create operator
292
			Operator op = new Operator(solution);
293
			
294
			try {
295
				
296
				// propagate operator
297
				this.pdb.propagate(op);
298
				// get plan with updated temporal bounds and variable binding
299
				Plan plan = this.pdb.getPlan();
300
				// create a child search space node
301
				SearchSpaceNode child = new SearchSpaceNode(current, op);
302
				// set partial plan
303
				child.setPartialPlan(plan);
304
				
305
				// look ahead of flaws representing the agenda of the node
306
				for (Flaw f : this.pdb.checkFlaws()) {
307
					// add checked flaw
308
					child.addCheckedFlaw(f);
309
				}
310
	
311
				// add child
312
				list.add(child);
313
				// retract operator
314
				this.pdb.retract(op);
315
				
316
			} catch (OperatorPropagationException ex) {
317
				// flaw with unsolvable solution
318
				throw new UnsolvableFlawException("Flaw with unsolvable solution found:\n- msg: " + ex.getMessage() + "\n");
319
			}
320
		}
321
		
322
		// get children
323
		return list;
324
	}
325
}
326