Revision 109:66adaba6c508

View differences:

src/main/java/cz/agents/dimaptools/landmarks/LMCutHeuristic.java
1
package cz.agents.dimaptools.landmarks;
2

  
3
import java.util.LinkedList;
4
import java.util.List;
5

  
6
import org.apache.log4j.Logger;
7

  
8
import cz.agents.dimaptools.domain.Problem;
9
import cz.agents.dimaptools.domain.State;
10
import cz.agents.dimaptools.domain.SuperState;
11
import cz.agents.dimaptools.heuristic.HeuristicInterface.HeuristicComputedCallback;
12
import cz.agents.dimaptools.heuristic.HeuristicResult;
13
import cz.agents.dimaptools.relaxed.Proposition;
14
import cz.agents.dimaptools.relaxed.RelaxationHeuristic;
15
import cz.agents.dimaptools.relaxed.UnaryOperator;
16

  
17
public class LMCutHeuristic extends RelaxationHeuristic{
18
	
19
	private final Logger LOGGER = Logger.getLogger(LMCutHeuristic.class);
20
	
21
	
22
	private Proposition artificialGoal;
23
	private UnaryOperator goalOperator;
24

  
25
	public LMCutHeuristic(Problem problem) {
26
		super(problem);
27
		
28
//		LOGGER = Logger.getLogger(problem.agent + "." + LMCutHeuristic.class);
29
		
30
		buildGoalPropositions(problem.goalSuperState);
31
		buildArtificialGoal(problem.goalSuperState);
32
	}
33
	
34
	public void buildArtificialGoal(SuperState goal){
35
		//TODO: cleanup
36
		
37
		artificialGoal = new Proposition(propositions.size()+1,-1,-1);
38
		artificialGoal.is_goal = true;
39
		artificialGoal.cost = -1;
40
		goalOperator = new UnaryOperator(operators.size()+1, -1, problem.agent);
41
		goalOperator.precondition = new LinkedList<Proposition>();
42
		goalOperator.effect = artificialGoal;
43
//		artificialGoal.reachedBy = goalOperator;
44
		operators.add(goalOperator);
45
		
46
		
47
		for(int var = 0; var < domain.sizeGlobal(); ++var){
48
			if(goal.isSet(var)){
49
				Proposition p = propositions.get(var).get(goal.getValue(var));
50
				goalOperator.precondition.add(p);
51
				p.preconditionOf.add(goalOperator);
52
			}
53
		}
54
		
55
		goalPropositions.add(artificialGoal);
56

  
57
	}
58

  
59
	@Override
60
	public void getHeuristic(State state, HeuristicComputedCallback callback) {
61
		int totalCost = 0;
62
		
63
		setupExplorationQueue();
64
		setupExplorationQueueState(state);
65

  
66
	    // The following two variables could be declared inside the loop
67
	    // ("second_exploration_queue" even inside second_exploration),
68
	    // but having them here saves reallocations and hence provides a
69
	    // measurable speed boost.
70
	    List<UnaryOperator> cut = new LinkedList<UnaryOperator>();
71
	    LinkedList<Proposition> secondExplorationQueue = new LinkedList<Proposition>();
72
	    firstExploration(state);
73
	    // validate_h_max();  // too expensive to use even in regular debug mode
74
	    if (artificialGoal.cost == -1){
75
	        callback.heuristicComputed(new HeuristicResult(LARGE_HEURISTIC,null));
76
	        return;
77
	    }
78

  
79
	    int num_iterations = 0;
80
	    while (artificialGoal.cost != 0) {
81
	        num_iterations++;
82
	        //cout << "h_max = " << artificial_goal.h_max_cost << "..." << endl;
83
	        //cout << "total_cost = " << total_cost << "..." << endl;
84
//	        mark_goal_plateau(&artificial_goal);
85
	        
86
	        secondExploration(state, secondExplorationQueue, cut);
87
	        
88
	        if(cut.isEmpty()){
89
	        	LOGGER.warn("Cut is empty!");
90
	        }else{
91
	        	LOGGER.info("Cut:\n");
92
	        	LOGGER.info(cut);
93
	        	for(UnaryOperator op : cut){
94
	        		LOGGER.info("     " + problem.getAction(op.actionHash) + "\n");
95
	        	}
96
	        }
97
	        
98
	        int cut_cost = Integer.MAX_VALUE;
99
	        for (UnaryOperator op : cut) {
100
	            cut_cost = Math.min(cut_cost, op.cost);
101
	        }
102
	        for (UnaryOperator op : cut){
103
	        	op.cost -= cut_cost;
104
	        }
105
	        //cout << "{" << cut_cost << "}" << flush;
106
	        totalCost += cut_cost;
107

  
108
	        firstExplorationIncremental(cut);
109
	        // validate_h_max();  // too expensive to use even in regular debug mode
110
	        // TODO: Need better name for all explorations; e.g. this could
111
	        //       be "recompute_h_max"; second_exploration could be
112
	        //       "mark_zones" or whatever.
113
	        cut.clear();
114

  
115
	        // TODO: Make this more efficient. For example, we can use
116
	        //       a round-dependent counter for GOAL_ZONE and BEFORE_GOAL_ZONE,
117
	        //       or something based on total_cost, in which case we don't
118
	        //       need a per-round reinitialization.
119
//	        for (int var = 0; var < propositions.size(); var++) {
120
//	            for (int value = 0; value < propositions[var].size(); value++) {
121
//	                RelaxedProposition &prop = propositions[var][value];
122
//	                if (prop.status == GOAL_ZONE || prop.status == BEFORE_GOAL_ZONE)
123
//	                    prop.status = REACHED;
124
//	            }
125
//	        }
126
//	        artificial_goal.status = REACHED;
127
//	        artificial_precondition.status = REACHED;
128
	    }
129
	    //cout << "[" << total_cost << "]" << flush;
130
	    //cout << "**************************" << endl;
131
	    
132
	    LOGGER.info(domain.agent + " LMCut: " + totalCost);
133
	    
134
	    callback.heuristicComputed(new HeuristicResult(totalCost,null));
135
	}
136
	
137
	@Override
138
	public void evaluateOperators(List<UnaryOperator> operators, int proposition_cost) {
139
		for(UnaryOperator op : operators){
140
			op.cost = Math.max(proposition_cost + op.base_cost,op.cost);
141
		}
142

  
143
	}
144
	
145
	private void firstExploration(State state) {
146
		while(!explorationQueue.isEmpty()){
147
			Proposition p = explorationQueue.poll();
148
			
149
			if(p.equals(artificialGoal)){
150
				System.out.println("!");
151
			}
152

  
153
			if(p.cost < p.distance) continue;
154

  
155
//			if(artificialGoal.cost >= 0){
156
//				return;
157
//			}
158

  
159
			//compute cost
160
			evaluateOperators(p.preconditionOf, p.cost);
161

  
162
			//trigger operators
163
			for(UnaryOperator op : p.preconditionOf){
164
				op.setHMaxSupporter(p, p.cost);
165
				--op.unsatisfied_preconditions;
166
				if(op.unsatisfied_preconditions == 0){
167
					enqueueIfNecessary(op.effect,op.cost,op);
168
				}
169
			}
170
		}
171
	}
172
	
173
	private void firstExplorationIncremental(List<UnaryOperator> cut) {
174
		
175
		for (UnaryOperator op : cut) {
176
	        int cost = op.hMaxSupporterCost + op.cost;
177
	        SuperState eff = problem.getAction(op.actionHash).getEffect();
178
	        for(int var : eff.getSetVariableNames().toArray()){
179
	        	Proposition p = propositions.get(var).get(eff.getValue(var));
180
	        	enqueueIfNecessary(p, cost,p.reachedBy);
181
	        }
182
	    }
183
		
184
		while(!explorationQueue.isEmpty()){
185
			Proposition p = explorationQueue.poll();
186

  
187
			if(p.cost < p.distance) continue;
188

  
189
			//trigger operators
190
			for(UnaryOperator op : p.preconditionOf){
191
				if(op.hMaxSupporter.equals(p)){
192
					int old_supp_cost = op.hMaxSupporterCost;
193
	                if(old_supp_cost > p.cost){
194
	                    op.updateHMaxSupporter();
195
	                    int new_supp_cost = op.hMaxSupporterCost;
196
	                    if (new_supp_cost != old_supp_cost) {
197
	                        int target_cost = new_supp_cost + op.cost;
198
	                        if(op.actionHash != -1){
199
		                        SuperState eff =  problem.getAction(op.actionHash).getEffect();
200
		            	        for(int var : eff.getSetVariableNames().toArray()){
201
		            	        	Proposition e = propositions.get(var).get(eff.getValue(var));
202
		            	        	enqueueIfNecessary(e, target_cost,e.reachedBy);
203
		            	        }
204
	                        }else{
205
	            	        	enqueueIfNecessary(goalOperator.effect, target_cost,goalOperator);
206
	                        }
207
	                    }
208
	                }
209
				}
210
			}
211
		}
212
	}
213
	
214

  
215
	private void secondExploration(State state,LinkedList<Proposition> secondExplorationQueue,List<UnaryOperator> cut) {
216
		for(UnaryOperator op : operators){
217
			if(op.precondition.size() == 0){
218
				secondExplorationQueue.push(op.effect);
219
			}
220
		}
221
		
222
		for(int var = 0; var < domain.sizeGlobal(); ++var){
223
			if(state.isSet(var) && domain.inDomainVar(var)){
224
				Proposition p = propositions.get(var).get(state.getValue(var));
225
				secondExplorationQueue.push(p);
226
			}
227
		}
228
		
229
		while(!secondExplorationQueue.isEmpty()){
230
			Proposition p = secondExplorationQueue.pop();
231
			//trigger operators
232
			for(UnaryOperator op : p.preconditionOf){
233
				if(op.hMaxSupporter.equals(p)){
234
					boolean reachedGoalZone = false;
235
					if(goalPropositions.contains(op.effect)){
236
						reachedGoalZone = true;
237
						cut.add(op);
238
					}
239
	                if (!reachedGoalZone) {
240
	                	secondExplorationQueue.push(op.effect);
241
	                }
242
				}
243
			}
244
		}
245
		
246
	}
247

  
248
	@Override
249
	public int getTotalCost() {
250
		LOGGER.warn("method not implemented!");
251
		return 0;
252
	}
253
	
254
	@Override
255
	public void processMessages() {
256
		
257
	}
258

  
259
	
260

  
261
	
262

  
263
	
264

  
265
	
266

  
267
	
268

  
269
}
src/main/java/cz/agents/dimaptools/relaxed/Proposition.java
62 62

  
63 63
	@Override
64 64
	public String toString() {
65
		return "Proposition [var=" + var + ", val=" + val + "]";
65
		return "Proposition [var=" + var + ", val=" + val + "]:"+cost+"/"+distance;
66 66
	}
67 67

  
68 68

  
src/main/java/cz/agents/dimaptools/relaxed/UnaryOperator.java
9 9
	public final int base_cost = 1;
10 10

  
11 11
	public int unsatisfied_preconditions;
12
	public int cost;
12
	public int cost = -1;
13 13

  
14 14
	String agent;
15 15

  
16 16
	public List<Proposition> precondition;
17 17
	public Proposition effect;
18
	
19
	public int hMaxSupporterCost;
20
	public Proposition hMaxSupporter;
18 21

  
19 22

  
20 23
	public UnaryOperator(int operatorNo, int actionHash, String agent) {
......
23 26
		this.actionHash = actionHash;
24 27
		this.agent = agent;
25 28
	}
29
	
30
	public void setHMaxSupporter(Proposition supporter, int cost){
31
		hMaxSupporter = supporter;
32
		hMaxSupporterCost = cost;
33
	}
34

  
35
	public void updateHMaxSupporter() {
36
		for (Proposition p : precondition){
37
	        if (p.distance > hMaxSupporter.distance){
38
	        	hMaxSupporter = p;
39
	        }
40
		}
41
		hMaxSupporterCost = hMaxSupporter.distance;
42
	}
26 43

  
27 44

  
28 45
	@Override
src/test/java/cz/agents/dimaptools/landmarks/TestLMCutHeuristic.java
1
package cz.agents.dimaptools.landmarks;
2

  
3
import org.junit.Test;
4

  
5
import cz.agents.alite.configurator.MapConfiguration;
6
import cz.agents.dimaptools.DIMAPWorldInterface;
7
import cz.agents.dimaptools.heuristic.HeuristicInterface;
8
import cz.agents.dimaptools.search.AbstractDistributedAStarTest;
9
import cz.agents.dimaptools.search.DistributedAStar;
10

  
11
public class TestLMCutHeuristic extends AbstractDistributedAStarTest {
12

  
13
	@Test
14
	public void test() {
15
		testProblem("truck-a1");
16
//		testProblem("truck-crane-a2");
17
//		testProblem("logistics-a2");
18
//		testProblem("logistics-a4");
19
//		testProblem("deconfliction-a4");
20
//		testProblem("rovers-a4");
21
//		testProblem("sokoban-a1");
22
//		testProblem("sokoban-a2");
23
	}
24

  
25
	@Override
26
	public void runSearch(DIMAPWorldInterface world){
27
		DistributedAStar search = new DistributedAStar(world);
28
//		AStar search = new AStar(problem);
29

  
30
		HeuristicInterface heuristic = new LMCutHeuristic(world.getProblem());
31

  
32
		search.plan(new MapConfiguration("heuristic",heuristic), searchCallback);
33
	}
34

  
35
}

Also available in: Unified diff