Revision 346:c5a4313b5cb7

View differences:

src/main/java/cz/agents/dimaptools/heuristic/landmarks/JustificationGraph.java
8 8
import java.util.Map;
9 9
import java.util.Set;
10 10

  
11
import org.apache.log4j.Logger;
12

  
11 13
import cz.agents.dimaptools.heuristic.relaxed.Proposition;
12 14
import cz.agents.dimaptools.heuristic.relaxed.UnaryOperator;
13 15
import cz.agents.dimaptools.model.SuperState;
14 16

  
15 17
public class JustificationGraph {
16 18
	
19

  
20
	private final Logger LOGGER = Logger.getLogger(JustificationGraph.class);
21
	
17 22
	Map<Integer,Map<Integer,JGNode>> nodes = new HashMap<>();
18 23
	Set<JGEdge> edges = new HashSet<>();
19 24
	
......
21 26
	JGNode g = new JGNode("g");
22 27
	
23 28
	public JustificationGraph(ArrayList<UnaryOperator> operators, Map<Integer,Map<Integer,Proposition>> propositions,SuperState currentState,ArrayList<Proposition> goalPropositions){
29
		
30
		
31
		
24 32
		for(UnaryOperator op : operators){
25 33
			
26
			if(op.precondition.isEmpty() || op.effect == null) continue;
34
//			LOGGER.info("add operator("+op.actionHash+"): " + op);
27 35
			
28
			Proposition maxPre = null;
29
			for(Proposition pre : op.precondition){
30
				if(maxPre == null){
31
					maxPre = pre;
32
				}else{
33
					maxPre = pre.cost > maxPre.cost ? pre : maxPre;
36
			if(op.effect == null) continue;
37
			
38
			JGNode pre;
39
			
40
			if(!op.precondition.isEmpty()){
41
				Proposition maxPre = null;
42
				for(Proposition p : op.precondition){
43
					if(maxPre == null){
44
						maxPre = p;
45
					}else{
46
						maxPre = p.cost > maxPre.cost ? p : maxPre;
47
					}
34 48
				}
49
				
50
				pre = getNode(maxPre);
51
			}else{
52
				pre = i;
35 53
			}
36 54
			
37
			JGNode pre = getNode(maxPre);
38 55
			JGNode eff = getNode(op.effect);
39 56
			
40 57
			addEdge(pre, eff, op);
......
42 59
		
43 60
		for(int var: currentState.getSetVariableNames().toArray()){
44 61
			JGNode init = getNode(var, currentState.getValue(var));
45
			addEdge(i, init, new UnaryOperator(-1, -1, null, 0, false));
62
			boolean add = true;
63
			for(JGEdge e : i.out){
64
				if(e.to.equals(init)){
65
					add = false;
66
					break;
67
				}
68
			}
69
			if(add){
70
				addEdge(i, init, new UnaryOperator(-1, -1, null, 0, false));
71
			}
46 72
		}
47 73
		
48 74
		for(Proposition p : goalPropositions){
49 75
			JGNode goal = getNode(p);
50
			addEdge(goal, g, new UnaryOperator(-1, -1, null, 0, false));
76
			boolean add = true;
77
			for(JGEdge e : goal.out){
78
				if(e.to.equals(g)){
79
					add = false;
80
					break;
81
				}
82
			}
83
			if(add){
84
				addEdge(goal, g, new UnaryOperator(-1, -1, null, 0, false));
85
			}
51 86
		}
52 87
		
53 88
		g.zeroReachableFromGoal = true;
......
131 166
			
132 167
			for(JGEdge e : n.out){
133 168
				if(e.to.zeroReachableFromGoal){
169
//					LOGGER.info(" ...cut edge: "+ e);
134 170
					cut.addAll(e.labels);
135 171
				}else{
136 172
					if(!closed.contains(e.to)){
......
189 225
		
190 226
		@Override
191 227
		public String toString() {
192
			return from+"->"+to+":"+zeroCost;
228
			return from+"->"+to+":"+zeroCost+","+labels;
193 229
		}
194 230
		
195 231
		
src/main/java/cz/agents/dimaptools/heuristic/landmarks/LMCutHeuristic.java
35 35
		
36 36
		LOGGER = Logger.getLogger(agent + "." + LMCutHeuristic.class);
37 37
		
38
		cf = new HashMap<>();
39
		
38 40
		for(Action a : problem.getAllActions()){
39 41
			cf.put(a.hashCode(), (int)a.getCost());
40 42
		}
41 43
		
44
		cf.put(-1,0);//dummy actions
45
		
42 46
	}
43 47
	
44 48
	private Set<UnaryOperator> computeNextLandmark(State s){
45 49
		LOGGER.info(agent + " compute hmax...");
46
		LOGGER.info(agent + " cost function:"+cf);
50
		if(LOGGER.isInfoEnabled())LOGGER.info(agent + " cost function:"+cf);
47 51
		
48 52
		RelaxationHeuristic hmax = new RelaxationHeuristic(problem, new MaxEvaluator(problem),false,cf);
49 53
		hmax.getHeuristic(s, new HeuristicComputedCallback() {
......
56 60
		
57 61
		LOGGER.info(agent + " hmax="+hmaxValue);
58 62
		
63
		if(hmaxValue == 0){
64
			return null;
65
		}
66
		
59 67
		LOGGER.info(agent + " build justification graph...");
60 68
		
61 69
		JustificationGraph JG = new JustificationGraph(hmax.getOperators(),hmax.getPropositions(), s, hmax.getGoalPropositions());
70
//		LOGGER.info(agent +":"+JG);
62 71
		
63 72
		LOGGER.info(agent + " find cut...");
64 73
		
......
77 86
		while(hmaxValue > 0){
78 87
			LOGGER.info(agent + " - LMCut("+iteration+"):");
79 88
			Set<UnaryOperator> lm = computeNextLandmark(state);
89
			
90
			if(lm == null){
91
				LOGGER.info(agent + " hmax == 0 -> break");
92
				break;
93
			}
94
			
95
			if(lm.isEmpty()){
96
				LOGGER.warn(agent + " EMPTY LANDMARK!");
97
				break;
98
			}
99
			
100
			LOGGER.info(agent + " new cut:" + lm);
101
			
80 102
			landmarks.add(lm);
81 103
			
82
			
83
			
84 104
			int lmCost = Integer.MAX_VALUE;
85 105
			for(UnaryOperator op : lm){
106
			
86 107
				int cost = cf.get(op.actionHash);
87 108
				lmCost = cost < lmCost ? cost : lmCost;
109
				
88 110
			}
89 111
			for(UnaryOperator op : lm){
90 112
				cf.put(op.actionHash,cf.get(op.actionHash)-lmCost);
91 113
			}
92 114
			
93
			LOGGER.info("LM("+iteration+"): " + lm + ", cost:" + lmCost);
115
			LOGGER.info(agent + " LM("+iteration+")="+lmCost+": " + lm);
116
			
117
			if(lmCost == 0){
118
				LOGGER.warn(agent + " LANDMARK COST == 0!");
119
				break;
120
			}
94 121
			
95 122
			h += lmCost;
96 123
			++ iteration;
src/main/java/cz/agents/dimaptools/heuristic/relaxed/RelaxationHeuristic.java
174 174
	private void buildOperator(List<Proposition> pre, int var, Action a){
175 175
		int cost = costFunction == null ? (int)a.getCost() : costFunction.get(a.hashCode());
176 176
		UnaryOperator op = new UnaryOperator(operators.size(),a.hashCode(),a.getOwner(),cost,a.isProjection() && !a.isPure());
177
//		LOGGER.info("HMAX new OPERATOR:  " + op);
177 178
		op.precondition = pre;
178 179
		op.effect = propositions.get(var).get(a.getEffect().getValue(var));
179 180
		operators.add(op);
src/main/java/cz/agents/dimaptools/heuristic/relaxed/UnaryOperator.java
52 52

  
53 53
    @Override
54 54
    public String toString() {
55
        return "UnaryOperator [operatorNo=" + operatorsIndex
56
                + ", unsatisfied_preconditions=" + unsatisfied_preconditions
57
                + ", cost=" + cost + ", agent=" + agent + ", precondition="
58
                + precondition + ", effect=" + effect + "]";
55
//        return "UnaryOperator [operatorNo=" + operatorsIndex +",hash=" + actionHash
56
//                + ", unsatisfied_preconditions=" + unsatisfied_preconditions
57
//                + ", cost=" + cost + ", agent=" + agent + ", precondition="
58
//                + precondition + ", effect=" + effect + "]";
59
        
60
        return "UnaryOperator [hash=" + actionHash
61
                + ", baseCost=" + baseCost + ", agent=" + agent + "]";
59 62
    }
60 63

  
61 64

  
src/test/java/cz/agents/dimaptools/landmarks/TestLMCutHeuristic.java
6 6
import cz.agents.dimaptools.DIMAPWorldInterface;
7 7
import cz.agents.dimaptools.heuristic.HeuristicInterface;
8 8
import cz.agents.dimaptools.heuristic.landmarks.LMCutHeuristic;
9
import cz.agents.dimaptools.search.AStar;
10 9
import cz.agents.dimaptools.search.AbstractDistributedAStarTest;
10
import cz.agents.dimaptools.search.DistributedBestFirstSearch;
11 11

  
12 12
public class TestLMCutHeuristic extends AbstractDistributedAStarTest {
13 13

  
......
15 15
	public void test() {
16 16
//		testProblem("truck-a1");
17 17
//		testProblem("truck-crane-a2");
18
		testProblem("logistics-a2");
19
//		testProblem("logistics-a4");
18
//		testProblem("logistics-a2");
19
		testProblem("logistics-a4");
20 20
//		testProblem("deconfliction-a4");
21 21
//		testProblem("rovers-a4");
22 22
//		testProblem("sokoban-a1");
......
25 25

  
26 26
	@Override
27 27
	public void runSearch(DIMAPWorldInterface world){
28
//		DistributedBestFirstSearch search = new DistributedBestFirstSearch(world);
29
		AStar search = new AStar(world.getProblem());
28
		DistributedBestFirstSearch search = new DistributedBestFirstSearch(world);
29
//		AStar search = new AStar(world.getProblem());
30 30

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

  

Also available in: Unified diff