Revision 177:92ccd419615b

View differences:

src/main/java/cz/agents/dimaptools/search/DistributedBestFirstSearch.java
55 55
    protected final DistributedSearchProtocol protocol;
56 56

  
57 57
    protected String bestReconstructedPlanBy = null;
58
    protected int bestReconstructedPlanCost;
58
    protected int bestReconstructedPlanCost = Integer.MAX_VALUE;
59 59

  
60 60
    protected long timeLimitMs = Long.MAX_VALUE;
61 61

  
src/main/java/cz/agents/dimaptools/search/HeuristicOpenList.java
7 7
import cz.agents.dimaptools.heuristic.HeuristicInterface.HeuristicComputedCallback;
8 8
import cz.agents.dimaptools.model.State;
9 9

  
10
public class HeuristicOpenList{
10
public class HeuristicOpenList implements Comparable<HeuristicOpenList>{
11 11
	public final String label;
12 12
	private final int hash;
13 13
	private final PriorityBlockingQueue<SearchState> open;
......
75 75
		
76 76
	}
77 77
	
78
	/*
79
	 * TODO: this does not make sense! if a state is preferred must be determined by which 
80
	 * operator it was created, no form which queue it was pulled 
81
	 * - in normal queue are both preferred and normal states. The way it is implemented, once
82
	 * a queue is polled, it will most probably be allways polled (until its empty)
83
	 */
78 84
	public boolean polledPreferred() {
79 85
		return polledPreferred;
80 86
	}
81 87
	
82 88
	public void boost(boolean boostPreferred) {
89
		
83 90
		if(boostPreferred){
84 91
			preOpenPriority += 1000;  
85 92
//			System.out.println("boost preferred: " + preOpenPriority + ", normal: " + openPriority);
......
87 94
			openPriority += 1000; 
88 95
//			System.out.println("boost normal: " + openPriority + ", preferred: " + preOpenPriority);
89 96
		}
97
		System.out.println("boost "+label+"("+boostPreferred+"), preferred: " + preOpenPriority + ", normal: " + openPriority);
90 98
	}
91 99
	
92 100
	public void add(SearchState state, boolean helpful){
......
111 119
		heuristic.processMessages();
112 120
		requestHeuristic.processMessages();
113 121
	}
122
	
123
	public int getPriority(){
124
		return Math.max(openPriority, preOpenPriority);
125
	}
126
	
127
	@Override
128
	public int compareTo(HeuristicOpenList o) {
129
		return getPriority() - o.getPriority();
130
	}
114 131

  
115 132
	@Override
116 133
	public int hashCode() {
......
143 160

  
144 161
	
145 162

  
163
	
164

  
146 165
}
src/main/java/cz/agents/dimaptools/search/MultiheuristicDistributedBestFirstSearch.java
27 27
    private static final Logger LOGGER = Logger.getLogger(MultiheuristicDistributedBestFirstSearch.class);
28 28

  
29 29
    private final ArrayList<HeuristicOpenList> openLists = new ArrayList<HeuristicOpenList>();
30

  
30
    
31 31
    private int currentOpenList = 0;
32
    private OpenSelectionStrategy strategy = OpenSelectionStrategy.ALTERNATE;
33
    
34
    public enum OpenSelectionStrategy {
35
    	ALTERNATE,
36
    	PREFFERENCE
37
    }
32 38

  
33 39

  
34 40

  
......
73 79
        }
74 80

  
75 81
        for(String key : config.getKeyList()){
76
            if(!key.equals("preferred")){
82
            if(!key.equals("preferred") && !key.equals("openSelectionStrategy")){
77 83
                openLists.add((HeuristicOpenList)config.getObject(key));
78 84
            }
79 85
        }
86
        
87
        strategy = OpenSelectionStrategy.valueOf(config.getString("openSelectionStrategy", OpenSelectionStrategy.ALTERNATE.name()));
88
        
80 89

  
81 90
    }
82 91

  
......
97 106

  
98 107
                state = openLists.get(currentOpenList).pollOpen();
99 108
                
100
                if(state.getHeuristic() < minH){
101
	              	minH = state.getHeuristic();
102
	               	if(LOGGER.isInfoEnabled())LOGGER.info("Reached new minimal [" + state.getParentActionOwner() + "] /h/: " + minH);
103
	            }
104
	            if(state.getG() > maxG){
105
	               	maxG = state.getG();
106
	               	if(LOGGER.isInfoEnabled())LOGGER.info("Reached new maximal [" + state.getParentActionOwner() + "] /g/: " + maxG);
107
	            }
108

  
109
                if(state==null && strategy != OpenSelectionStrategy.ALTERNATE){
110
                	currentOpenList = (currentOpenList + 1) % openLists.size();
111
                }
112
                
109 113
                if (state != null && !closed.contains(state.hashCode())) {
114
                	
115
                	if(state.getHeuristic() < minH){
116
    	              	minH = state.getHeuristic();
117
    	               	if(LOGGER.isInfoEnabled())LOGGER.info("Reached new minimal [" + state.getParentActionOwner() + "] /h/: " + minH);
118
    	            }
119
    	            if(state.getG() > maxG){
120
    	               	maxG = state.getG();
121
    	               	if(LOGGER.isInfoEnabled())LOGGER.info("Reached new maximal [" + state.getParentActionOwner() + "] /g/: " + maxG);
122
    	            }
110 123

  
111 124
                    closed.add(state.hashCode());
112 125

  
......
144 157

  
145 158

  
146 159
                    final boolean stateIsPreferred = openLists.get(currentOpenList).polledPreferred();
147

  
148
                    for(final HeuristicOpenList open : openLists){
160
                    
161
                    int bestOpenPriority = 0;
162
                    
163
                    for(int ol=0; ol < openLists.size(); ol++){
164
                    	final HeuristicOpenList open = openLists.get(ol);
149 165

  
150 166
//		        		LOGGER.info(comm.getAddress() + "("+open.label+") get heuristic of state " + state.hashCode());
151 167

  
......
212 228

  
213 229
                            }
214 230
                        });
231
                        
232
                        if(strategy == OpenSelectionStrategy.PREFFERENCE && open.getPriority() > bestOpenPriority){
233
                        	bestOpenPriority = open.getPriority();
234
                        	currentOpenList = ol;
235
                        }
215 236
                    }
216 237

  
217 238
                }
......
229 250
            commPerformer.performReceive();
230 251

  
231 252
            if(search){
232
                openLists.get(currentOpenList).processMessages();
253
            	for(HeuristicOpenList openList : openLists){
254
            		openList.processMessages();
255
            	}
233 256
            }
234 257

  
235
            currentOpenList = (currentOpenList + 1) % openLists.size();
258
            if(strategy == OpenSelectionStrategy.ALTERNATE){
259
            	currentOpenList = (currentOpenList + 1) % openLists.size();
260
            }
236 261

  
237 262
        }while(run);
238 263

  
src/test/java/cz/agents/dimaptools/multiheuristic/TestFFrdFFHeuristicMPrefference.java
1
package cz.agents.dimaptools.multiheuristic;
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.relaxed.RecursiveDistributedRelaxationReplyHeuristic;
8
import cz.agents.dimaptools.heuristic.relaxed.RecursiveDistributedRelaxationRequestHeuristic;
9
import cz.agents.dimaptools.heuristic.relaxed.RelaxationHeuristic;
10
import cz.agents.dimaptools.heuristic.relaxed.evaluator.AddEvaluator;
11
import cz.agents.dimaptools.heuristic.relaxed.evaluator.FFEvaluator;
12
import cz.agents.dimaptools.search.AbstractDistributedAStarTest;
13
import cz.agents.dimaptools.search.HeuristicOpenList;
14
import cz.agents.dimaptools.search.MultiheuristicDistributedBestFirstSearch;
15
import cz.agents.dimaptools.search.MultiheuristicDistributedBestFirstSearch.OpenSelectionStrategy;
16

  
17
public class TestFFrdFFHeuristicMPrefference extends AbstractDistributedAStarTest {
18

  
19
    @Test
20
    public void test() {
21
//		testProblem("truck-crane-a2");
22
//		testProblem("logistics-a2");
23
//		testProblem("logistics-a4");
24
//		testProblem("deconfliction-a4");
25
		testProblem("rovers-a4");
26
//		testProblem("sokoban-a1");
27
//		testProblem("sokoban-a2");
28
    }
29

  
30
    @Override
31
    public void runSearch(DIMAPWorldInterface world){
32
        MultiheuristicDistributedBestFirstSearch search = new MultiheuristicDistributedBestFirstSearch(world);
33

  
34
        HeuristicOpenList hFF = new HeuristicOpenList("hFF",true,new RelaxationHeuristic(world.getProblem(), new FFEvaluator(world.getProblem())));
35

  
36
        new HeuristicOpenList("hAdd",false,new RelaxationHeuristic(world.getProblem(),new AddEvaluator(world.getProblem(),false)));
37
//		HeuristicOpenList hAdd = new HeuristicOpenList("hAdd",false,new RelaxationHeuristic(world.getProblem(),new AddEvaluator(world.getProblem(),false)));
38

  
39
        RecursiveDistributedRelaxationRequestHeuristic req = new RecursiveDistributedRelaxationRequestHeuristic(world, new FFEvaluator(world.getProblem()));
40
        RecursiveDistributedRelaxationReplyHeuristic rep = new RecursiveDistributedRelaxationReplyHeuristic(world, new FFEvaluator(world.getProblem()),req.getRequestProtocol());
41
        req.setReplyProtocol(rep.getReplyProtocol());
42

  
43
        HeuristicOpenList hrdFF = new HeuristicOpenList("hrdFF",true,req,rep);
44

  
45
//		search.plan(new MapConfiguration("hFF",hFF,"hAdd",hAdd), searchCallback);
46

  
47
//		search.plan(new MapConfiguration("hFF",hFF), searchCallback);
48
//		search.plan(new MapConfiguration("hrdFF",hrdFF), searchCallback);
49
        search.plan(new MapConfiguration("hFF",hFF,"hrdFF",hrdFF,"openSelectionStrategy", OpenSelectionStrategy.PREFFERENCE.name()), searchCallback);
50
    }
51

  
52
}

Also available in: Unified diff