Revision 176:b1e9d09d6a03

View differences:

src/main/java/cz/agents/dimaptools/search/DistributedBestFirstSearch.java
40 40
    private static final Logger LOGGER = Logger.getLogger(DistributedBestFirstSearch.class);
41 41

  
42 42
    protected final Problem problem;
43
    private final PriorityBlockingQueue<SearchState> open = new PriorityBlockingQueue<SearchState>();
43
    protected final PriorityBlockingQueue<SearchState> open = new PriorityBlockingQueue<SearchState>();
44 44
    protected final TIntHashSet closed = new TIntHashSet();
45 45

  
46
    private HeuristicInterface heuristic;
47
    private HeuristicInterface requestHeuristic;
46
    protected HeuristicInterface heuristic;
47
    protected HeuristicInterface requestHeuristic;
48 48
    protected SearchCallback planCallback;
49 49

  
50 50

  
51 51
    protected final Communicator comm;
52 52
    protected final CommunicationPerformer commPerformer;
53
    private final TIntObjectHashMap sentStates = new TIntObjectHashMap();
53
    protected final TIntObjectHashMap sentStates = new TIntObjectHashMap();
54 54

  
55
    private final DistributedSearchProtocol protocol;
55
    protected final DistributedSearchProtocol protocol;
56 56

  
57
    private String bestReconstructedPlanBy = null;
58
    private int bestReconstructedPlanCost;
57
    protected String bestReconstructedPlanBy = null;
58
    protected int bestReconstructedPlanCost;
59 59

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

  
src/main/java/cz/agents/dimaptools/search/SyncDistributedBestFirstSearch.java
1 1
package cz.agents.dimaptools.search;
2 2

  
3
import gnu.trove.TIntHashSet;
4
import gnu.trove.TIntObjectHashMap;
5

  
6
import java.util.Arrays;
7
import java.util.HashSet;
8 3
import java.util.LinkedList;
9 4
import java.util.List;
10 5
import java.util.Set;
11
import java.util.concurrent.PriorityBlockingQueue;
12 6

  
13 7
import org.apache.log4j.Logger;
14 8

  
15
import cz.agents.alite.communication.CommunicationPerformer;
16
import cz.agents.alite.communication.Communicator;
17 9
import cz.agents.alite.configurator.ConfigurationInterface;
18 10
import cz.agents.dimaptools.DIMAPWorldInterface;
19
import cz.agents.dimaptools.communication.message.PlanningFinishedMessage;
20
import cz.agents.dimaptools.communication.message.ReconstructPlanMessage;
21 11
import cz.agents.dimaptools.communication.message.StateMessage;
22
import cz.agents.dimaptools.communication.protocol.DistributedSearchProtocol;
23 12
import cz.agents.dimaptools.experiment.DataAccumulator;
24 13
import cz.agents.dimaptools.heuristic.HeuristicInterface;
25 14
import cz.agents.dimaptools.heuristic.HeuristicInterface.HeuristicComputedCallback;
26 15
import cz.agents.dimaptools.heuristic.HeuristicResult;
27
import cz.agents.dimaptools.heuristic.goalsat.GoalSatHeuristic;
28
import cz.agents.dimaptools.model.Action;
29
import cz.agents.dimaptools.model.Problem;
30 16

  
31 17
/**
32 18
 * Simple implementation of distributed Best-First Search with deferred heuristic evaluation.
......
35 21
 * @author stolba
36 22
 *
37 23
 */
38
public class SyncDistributedBestFirstSearch implements SearchInterface, HeuristicComputedCallback {
24
public class SyncDistributedBestFirstSearch extends DistributedBestFirstSearch implements SearchInterface, HeuristicComputedCallback {
39 25

  
40 26
    private static final Logger LOGGER = Logger.getLogger(SyncDistributedBestFirstSearch.class);
41

  
42
    protected final Problem problem;
43
    private final PriorityBlockingQueue<SearchState> open = new PriorityBlockingQueue<SearchState>();
44
    protected final TIntHashSet closed = new TIntHashSet();
45

  
46
    private HeuristicInterface heuristic;
47
    private HeuristicInterface requestHeuristic;
48
    protected SearchCallback planCallback;
49

  
50

  
51
    protected final Communicator comm;
52
    protected final CommunicationPerformer commPerformer;
53
    private final TIntObjectHashMap sentStates = new TIntObjectHashMap();
54

  
55
    private final DistributedSearchProtocol protocol;
56

  
57
    private String bestReconstructedPlanBy = null;
58
    private int bestReconstructedPlanCost;
59

  
60
    protected long timeLimitMs = Long.MAX_VALUE;
61

  
62
    protected volatile boolean run = true;
63
    protected volatile boolean search = true;
27
    
28
	private SearchState state;
64 29

  
65 30
	private boolean heuristicComputed;
66
	private SearchState state;
67

  
68
	protected int minH = Integer.MAX_VALUE;
69
	protected int maxG = 0;
70

  
71

  
72

  
73 31

  
74 32
    public SyncDistributedBestFirstSearch(DIMAPWorldInterface world) {
75 33
        this(world,Long.MAX_VALUE);
76 34
    }
77 35

  
78 36
    public SyncDistributedBestFirstSearch(DIMAPWorldInterface world,long timeLimitMs) {
79
        this.problem = world.getProblem();
80
        this.comm = world.getCommunicator();
81
        commPerformer = world.getCommPerformer();
82
        this.timeLimitMs = timeLimitMs;
83

  
84
        heuristic = new GoalSatHeuristic(problem.goalSuperState);
85
        requestHeuristic = heuristic;
86

  
87
        protocol = new DistributedSearchProtocol(comm, world.getAgentName(), world.getEncoder()) {
88

  
89
            @Override
90
            public void receiveStateMessage(StateMessage sm, String sender) {
91
                if (!closed.contains(sm.getHash())) {
92

  
93
                    if(LOGGER.isDebugEnabled())LOGGER.debug(comm.getAddress() + " receive state " + Arrays.toString(sm.getValues()));
94

  
95
                    addReceivedState(sm, sender);
96

  
97
                }
98
            }
99

  
100
            @Override
101
            public void receiveReconstructPlanMessage(ReconstructPlanMessage rpm) {
102
                SearchState state = (SearchState)sentStates.get(rpm.getLastStateHash());
103

  
104
//            	LOGGER.info(comm.getAddress() + " receive reconstruct msg " + state.hashCode() );
105

  
106
                reconstructPlan(state, rpm.getPlan(),rpm.getInitiatorID(),rpm.getSolutionCost());
107

  
108
//            	run = false;
109
                search = false;
110
            }
111

  
112
            @Override
113
            public void receivePlanningFinishedMessage(PlanningFinishedMessage msg) {
114

  
115
                LOGGER.warn(comm.getAddress() + " receive PLANNING_FINISHED!" );
116

  
117

  
118
                run = false;
119

  
120
            }
121
        };
122

  
37
        super(world,timeLimitMs);
123 38

  
124 39
    }
125 40

  
......
252 167
		
253 168
	}
254 169

  
255
    /**
256
     * Distributed reconstruction of the plan
257
     * @param state
258
     * @param cost
259
     * @param initiator
260
     * @param plan
261
     */
262
    protected void reconstructPlan(SearchState state, List<String> globalPlan, String initiator, int solutionCost){
263
//		System.out.println(comm.getAddress() + " reconstruct " + state.hashCode() + " - " + plan);
264

  
265
        if(bestReconstructedPlanBy == null){
266
            bestReconstructedPlanBy = initiator;
267
            bestReconstructedPlanCost = solutionCost;
268
        }else{
269
            if(bestReconstructedPlanCost < solutionCost || bestReconstructedPlanBy.compareTo(initiator) < 0){
270
                LOGGER.info(comm.getAddress() +  " plan("+bestReconstructedPlanCost+") already reconstructed by "+initiator+" stop reconstruction of plan("+solutionCost+")");
271
                return;
272
            }
273
        }
274

  
275
        List<String> plan = new LinkedList<String>();
276
        ParentState lastState = state.reconstructPlan(plan);
277

  
278
        planCallback.partialPlanReconstructed(plan,initiator,solutionCost);
279

  
280
        plan.addAll(globalPlan);
281
        if(lastState.getParentActionOwner() == null){
282
            LOGGER.info(comm.getAddress() + " plan found " + state.hashCode() + " - " + plan);
283

  
284
            LOGGER.warn(comm.getAddress() + " send PLANNING_FINISHED!" );
285
            protocol.sendPlanningFinishedMessage();
286
            run = false;
287

  
288
            planCallback.planFound(plan);
289

  
290

  
291
        }else{
292

  
293
//        	LOGGER.info(comm.getAddress() + " send reconstruct msg " + state.hashCode() + " to " + lastState.getParentActionOwner());
294
            protocol.sendReconstructPlanMessage(new ReconstructPlanMessage(plan,lastState.hashCode(),initiator,solutionCost), lastState.getParentActionOwner());
295
        }
296
    }
297

  
298
    /**
299
     * Send reached state if reached by public action
300
     * @param state
301
     */
302
    public void sendState(final SearchState state){
303

  
304
        if(sentStates.containsKey(state.hashCode()))return;
305
        sentStates.put(state.hashCode(), state);
306

  
307
        StateMessage msg = new StateMessage(state.getValues(), state.getG(), state.getHeuristic());
308

  
309
        DataAccumulator.getAccumulator().searchMessages ++;
310
        DataAccumulator.getAccumulator().totalBytes += msg.getBytes();
311

  
312

  
313
//		protocol.sendStateMessage(msg,CommunicationChannelBroadcast.BROADCAST_ADDRESS);
314

  
315
        //send only to relevant agents
316
        Set<String> sentTo = new HashSet<String>();
317
        for(Action a : problem.getProjectedActions()){
318
            if(!sentTo.contains(a.getOwner()) && a.isApplicableIn(state)){
319
                protocol.sendStateMessage(msg,a.getOwner());
320
                sentTo.add(a.getOwner());
321
            }
322
        }
323
    }
324

  
325
    protected Set<SearchState> expand(SearchState state) {
326

  
327
//		LOGGER.info("expanding state with h=" + state.getHeuristic() + ", g+h=" + (state.getG()+state.getHeuristic()));
328

  
329
        Set<SearchState> result = new HashSet<SearchState>();
330

  
331
        for (Action action : problem.getMyActions()) {
332
            if (action.isApplicableIn(state)) {
333
                result.add(state.transformBy(action));
334
            }
335
        }
336

  
337
        return result;
338
    }
339

  
340
    protected boolean solutionFound(SearchState state) {
341
        if (state.unifiesWith(problem.goalSuperState)) {
342
            LOGGER.info("SOLUTION of cost "+state.getG()+" FOUND[" + problem.agent + "]: " + Arrays.toString(state.getValues()));
343

  
344
            LOGGER.info("OPEN-SIZE[" + problem.agent + "]" + open.size());
345
            LOGGER.info("CLOSED-SIZE[" + problem.agent + "]" + closed.size());
346

  
347
            return true;
348
        }
349

  
350
        return false;
351
    }
170
    
352 171

  
353 172
	
354 173

  

Also available in: Unified diff