source: src/main/java/agents/bayesianopponentmodel/BayesianOpponentModelScalable.java

Last change on this file was 127, checked in by Wouter Pasman, 6 years ago

#41 ROLL BACK of rev.126 . So this version is equal to rev. 125

File size: 17.5 KB
RevLine 
[127]1package agents.bayesianopponentmodel;
2
3import java.util.ArrayList;
4import java.util.List;
5
6import genius.core.Bid;
7import genius.core.issue.Issue;
8import genius.core.issue.IssueDiscrete;
9import genius.core.issue.IssueReal;
10import genius.core.utility.AdditiveUtilitySpace;
11import genius.core.utility.EVALFUNCTYPE;
12import genius.core.utility.EvaluatorDiscrete;
13import genius.core.utility.EvaluatorReal;
14
15/**
16 * Implementation of the scalable Bayesian Model.
17 *
18 * Opponent Modelling in Automated Multi-Issue Negotiation Using Bayesian
19 * Learning by K. Hindriks, D. Tykhonov
20 *
21 * KNOWN BUGS: 1. Opponent model does not take the opponent's strategy into
22 * account, in contrast to the original paper which depicts an assumption about
23 * the opponent'strategy which adapts over time.
24 *
25 * 2. The opponent model becomes invalid after a while as NaN occurs in some
26 * hypotheses, corrupting the overall estimation.
27 */
28public class BayesianOpponentModelScalable extends OpponentModel {
29
30 private AdditiveUtilitySpace fUS;
31 private ArrayList<ArrayList<WeightHypothesis2>> fWeightHyps;
32 private ArrayList<ArrayList<EvaluatorHypothesis>> fEvaluatorHyps;
33 // private ArrayList<EvaluatorHypothesis[]> fEvalHyps;
34 // public ArrayList<Bid> fBiddingHistory; // previous bids of the opponent,
35 // not our bids.
36 // private ArrayList<UtilitySpaceHypothesis> fUSHyps;
37 private double fPreviousBidUtility;
38 List<Issue> issues;
39 private double[] fExpectedWeights;
40
41 public BayesianOpponentModelScalable(AdditiveUtilitySpace pUtilitySpace) {
42 //
43
44 fPreviousBidUtility = 1;
45 fDomain = pUtilitySpace.getDomain();
46 issues = fDomain.getIssues();
47 fUS = pUtilitySpace;
48 fBiddingHistory = new ArrayList<Bid>();
49 fExpectedWeights = new double[pUtilitySpace.getDomain().getIssues()
50 .size()];
51 fWeightHyps = new ArrayList<ArrayList<WeightHypothesis2>>();
52 // generate all possible ordering combinations of the weights
53
54 initWeightHyps();
55 // generate all possible hyps of evaluation functions
56 fEvaluatorHyps = new ArrayList<ArrayList<EvaluatorHypothesis>>();
57 int lTotalTriangularFns = 4;
58 for (int i = 0; i < fUS.getNrOfEvaluators(); i++) {
59 ArrayList<EvaluatorHypothesis> lEvalHyps = new ArrayList<EvaluatorHypothesis>();
60
61 switch (fUS.getEvaluator(issues.get(i).getNumber()).getType()) {
62
63 case REAL:
64 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
65 fEvaluatorHyps.add(lEvalHyps);
66 // EvaluatorReal lEval = (EvaluatorReal)(fUS.getEvaluator(i));
67 IssueReal lIssue = (IssueReal) (fDomain.getIssues().get(i));
68 // uphill
69 EvaluatorReal lHypEval = new EvaluatorReal();
70 lHypEval.setUpperBound(lIssue.getUpperBound());
71 lHypEval.setLowerBound(lIssue.getLowerBound());
72 lHypEval.setType(EVALFUNCTYPE.LINEAR);
73 lHypEval.addParam(1, (double) 1
74 / (lHypEval.getUpperBound() - lHypEval.getLowerBound()));
75 lHypEval.addParam(
76 0,
77 -lHypEval.getLowerBound()
78 / (lHypEval.getUpperBound() - lHypEval
79 .getLowerBound()));
80 EvaluatorHypothesis lEvaluatorHypothesis = new EvaluatorHypothesis(
81 lHypEval);
82 lEvaluatorHypothesis.setDesc("uphill");
83 lEvalHyps.add(lEvaluatorHypothesis);
84 // downhill
85 lHypEval = new EvaluatorReal();
86 lHypEval.setUpperBound(lIssue.getUpperBound());
87 lHypEval.setLowerBound(lIssue.getLowerBound());
88 lHypEval.setType(EVALFUNCTYPE.LINEAR);
89 lHypEval.addParam(1, -(double) 1
90 / (lHypEval.getUpperBound() - lHypEval.getLowerBound()));
91 lHypEval.addParam(0, (double) 1 + lHypEval.getLowerBound()
92 / (lHypEval.getUpperBound() - lHypEval.getLowerBound()));
93 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
94 lEvalHyps.add(lEvaluatorHypothesis);
95 lEvaluatorHypothesis.setDesc("downhill");
96 for (int k = 1; k <= lTotalTriangularFns; k++) {
97 // triangular
98 lHypEval = new EvaluatorReal();
99 lHypEval.setUpperBound(lIssue.getUpperBound());
100 lHypEval.setLowerBound(lIssue.getLowerBound());
101 lHypEval.setType(EVALFUNCTYPE.TRIANGULAR);
102 lHypEval.addParam(0, lHypEval.getLowerBound());
103 lHypEval.addParam(1, lHypEval.getUpperBound());
104 double lMaxPoint = lHypEval.getLowerBound()
105 + (double) k
106 * (lHypEval.getUpperBound() - lHypEval
107 .getLowerBound())
108 / (lTotalTriangularFns + 1);
109 lHypEval.addParam(2, lMaxPoint);
110 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
111 lEvalHyps.add(lEvaluatorHypothesis);
112 lEvaluatorHypothesis.setDesc("triangular "
113 + String.format("%1.2f", lMaxPoint));
114 }
115 for (int k = 0; k < lEvalHyps.size(); k++) {
116 lEvalHyps.get(k).setProbability(
117 (double) 1 / lEvalHyps.size());
118 }
119
120 break;
121 case DISCRETE:
122 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
123 fEvaluatorHyps.add(lEvalHyps);
124 // EvaluatorReal lEval = (EvaluatorReal)(fUS.getEvaluator(i));
125 IssueDiscrete lDiscIssue = (IssueDiscrete) (fDomain.getIssues()
126 .get(i));
127 // uphill
128 EvaluatorDiscrete lDiscreteEval = new EvaluatorDiscrete();
129 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
130 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
131 1000 * j + 1);
132 lEvaluatorHypothesis = new EvaluatorHypothesis(lDiscreteEval);
133 lEvaluatorHypothesis.setProbability((double) 1 / 3);
134 lEvaluatorHypothesis.setDesc("uphill");
135 lEvalHyps.add(lEvaluatorHypothesis);
136 // downhill
137 lDiscreteEval = new EvaluatorDiscrete();
138 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
139 lDiscreteEval
140 .addEvaluation(
141 lDiscIssue.getValue(j),
142 1000 * (lDiscIssue.getNumberOfValues() - j - 1) + 1);
143 lEvaluatorHypothesis = new EvaluatorHypothesis(lDiscreteEval);
144 lEvaluatorHypothesis.setProbability((double) 1 / 3);
145 lEvalHyps.add(lEvaluatorHypothesis);
146 lEvaluatorHypothesis.setDesc("downhill");
147 if (lDiscIssue.getNumberOfValues() > 2) {
148 lTotalTriangularFns = lDiscIssue.getNumberOfValues() - 1;
149 for (int k = 1; k < lTotalTriangularFns; k++) {
150 // triangular. Wouter: we need to CHECK this.
151 lDiscreteEval = new EvaluatorDiscrete();
152 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
153 if (j < k) {
154 lDiscreteEval.addEvaluation(
155 lDiscIssue.getValue(j), 1000 * j / k);
156 } else {
157 // lEval =
158 // (1.0-(double)(j-k)/(lDiscIssue.getNumberOfValues()-1.0-k));
159 lDiscreteEval.addEvaluation(
160 lDiscIssue.getValue(j),
161 1000
162 * (lDiscIssue
163 .getNumberOfValues()
164 - j - 1)
165 / (lDiscIssue
166 .getNumberOfValues()
167 - k - 1) + 1);
168 }
169 lEvaluatorHypothesis = new EvaluatorHypothesis(
170 lDiscreteEval);
171 lEvalHyps.add(lEvaluatorHypothesis);
172 lEvaluatorHypothesis.setDesc("triangular "
173 + String.valueOf(k));
174 }// for
175 }// if
176 for (int k = 0; k < lEvalHyps.size(); k++) {
177 lEvalHyps.get(k).setProbability(
178 (double) 1 / lEvalHyps.size());
179 }
180 break;
181 }// switch
182 }
183 for (int i = 0; i < fExpectedWeights.length; i++)
184 fExpectedWeights[i] = getExpectedWeight(i);
185
186 // printEvalsDistribution();
187 }
188
189 void initWeightHyps() {
190 int lWeightHypsNumber = 11;
191 for (int i = 0; i < fUS.getDomain().getIssues().size(); i++) {
192 ArrayList<WeightHypothesis2> lWeightHyps = new ArrayList<WeightHypothesis2>();
193 for (int j = 0; j < lWeightHypsNumber; j++) {
194 WeightHypothesis2 lHyp = new WeightHypothesis2(fDomain);
195 lHyp.setProbability((1.0 - ((double) j + 1.0)
196 / lWeightHypsNumber)
197 * (1.0 - ((double) j + 1.0) / lWeightHypsNumber)
198 * (1.0 - ((double) j + 1.0) / lWeightHypsNumber));
199 lHyp.setWeight((double) j / (lWeightHypsNumber - 1));
200 lWeightHyps.add(lHyp);
201 }
202 double lN = 0;
203 for (int j = 0; j < lWeightHypsNumber; j++) {
204 lN += lWeightHyps.get(j).getProbability();
205 }
206 for (int j = 0; j < lWeightHypsNumber; j++) {
207 lWeightHyps.get(j).setProbability(
208 lWeightHyps.get(j).getProbability() / lN);
209 }
210
211 fWeightHyps.add(lWeightHyps);
212 }
213 }
214
215 private double conditionalDistribution(double pUtility,
216 double pPreviousBidUtility) {
217 // TODO: check this condition
218 // if(pPreviousBidUtility<pUtility) return 0;
219 // else {
220 double lSigma = 0.25;
221 double x = (pPreviousBidUtility - pUtility) / pPreviousBidUtility;
222 double lResult = 1.0 / (lSigma * Math.sqrt(2.0 * Math.PI))
223 * Math.exp(-(x * x) / (2.0 * lSigma * lSigma));
224 return lResult;
225 // }
226 }
227
228 public double getExpectedEvaluationValue(Bid pBid, int pIssueNumber)
229 throws Exception {
230 double lExpectedEval = 0;
231 for (int j = 0; j < fEvaluatorHyps.get(pIssueNumber).size(); j++) {
232 lExpectedEval = lExpectedEval
233 + fEvaluatorHyps.get(pIssueNumber).get(j).getProbability()
234 * fEvaluatorHyps
235 .get(pIssueNumber)
236 .get(j)
237 .getEvaluator()
238 .getEvaluation(fUS, pBid,
239 issues.get(pIssueNumber).getNumber());
240 }
241 return lExpectedEval;
242
243 }
244
245 public double getExpectedWeight(int pIssueNumber) {
246 double lExpectedWeight = 0;
247 for (int i = 0; i < fWeightHyps.get(pIssueNumber).size(); i++) {
248 lExpectedWeight += fWeightHyps.get(pIssueNumber).get(i)
249 .getProbability()
250 * fWeightHyps.get(pIssueNumber).get(i).getWeight();
251 }
252 return lExpectedWeight;
253 }
254
255 private double getPartialUtility(Bid pBid, int pIssueIndex)
256 throws Exception {
257 // calculate partial utility w/o issue pIssueIndex
258 double u = 0;
259 for (int j = 0; j < fDomain.getIssues().size(); j++) {
260 if (pIssueIndex == j)
261 continue;
262 // calculate expected weight of the issue
263 double w = 0;
264 for (int k = 0; k < fWeightHyps.get(j).size(); k++)
265 w += fWeightHyps.get(j).get(k).getProbability()
266 * fWeightHyps.get(j).get(k).getWeight();
267 u = u + w * getExpectedEvaluationValue(pBid, j);
268 }
269 return u;
270 }
271
272 public void updateWeights() throws Exception {
273 Bid lBid = fBiddingHistory.get(fBiddingHistory.size() - 1);
274 ArrayList<ArrayList<WeightHypothesis2>> lWeightHyps = new ArrayList<ArrayList<WeightHypothesis2>>();
275 // make new hyps array
276 for (int i = 0; i < fWeightHyps.size(); i++) {
277 ArrayList<WeightHypothesis2> lTmp = new ArrayList<WeightHypothesis2>();
278 for (int j = 0; j < fWeightHyps.get(i).size(); j++) {
279 WeightHypothesis2 lHyp = new WeightHypothesis2(fUS.getDomain());
280 lHyp.setWeight(fWeightHyps.get(i).get(j).getWeight());
281 lHyp.setProbability(fWeightHyps.get(i).get(j).getProbability());
282 lTmp.add(lHyp);
283 }
284 lWeightHyps.add(lTmp);
285 }
286
287 // for(int k=0;k<5;k++) {
288 for (int j = 0; j < fDomain.getIssues().size(); j++) {
289 double lN = 0;
290 double lUtility = 0;
291 for (int i = 0; i < fWeightHyps.get(j).size(); i++) {
292 // if(!lBid.getValue(j).equals(lPreviousBid.getValue(j))) {
293 lUtility = fWeightHyps.get(j).get(i).getWeight()
294 * getExpectedEvaluationValue(lBid, j)
295 + getPartialUtility(lBid, j);
296 lN += fWeightHyps.get(j).get(i).getProbability()
297 * conditionalDistribution(lUtility, fPreviousBidUtility);
298 /*
299 * } else { lN += fWeightHyps.get(j).get(i).getProbability(); }
300 */
301 }
302 // 2. receiveMessage probabilities
303 for (int i = 0; i < fWeightHyps.get(j).size(); i++) {
304 // if(!lBid.getValue(j).equals(lPreviousBid.getValue(j))) {
305 lUtility = fWeightHyps.get(j).get(i).getWeight()
306 * getExpectedEvaluationValue(lBid, j)
307 + getPartialUtility(lBid, j);
308 lWeightHyps
309 .get(j)
310 .get(i)
311 .setProbability(
312 fWeightHyps.get(j).get(i).getProbability()
313 * conditionalDistribution(lUtility,
314 fPreviousBidUtility) / lN);
315 /*
316 * } else {
317 * lWeightHyps.get(j).get(i).setProbability(fWeightHyps.
318 * get(j).get(i).getProbability()/lN); }
319 */
320 }
321 }
322 // }
323 fWeightHyps = lWeightHyps;
324 }
325
326 public void updateEvaluationFns() throws Exception {
327 Bid lBid = fBiddingHistory.get(fBiddingHistory.size() - 1);
328 // make new hyps array
329 // for(int k=0;k<5;k++){
330 ArrayList<ArrayList<EvaluatorHypothesis>> lEvaluatorHyps = new ArrayList<ArrayList<EvaluatorHypothesis>>();
331 for (int i = 0; i < fEvaluatorHyps.size(); i++) {
332 ArrayList<EvaluatorHypothesis> lTmp = new ArrayList<EvaluatorHypothesis>();
333 for (int j = 0; j < fEvaluatorHyps.get(i).size(); j++) {
334 EvaluatorHypothesis lHyp = new EvaluatorHypothesis(
335 fEvaluatorHyps.get(i).get(j).getEvaluator());
336 lHyp.setDesc(fEvaluatorHyps.get(i).get(j).getDesc());
337 lHyp.setProbability(fEvaluatorHyps.get(i).get(j)
338 .getProbability());
339 lTmp.add(lHyp);
340 }
341 lEvaluatorHyps.add(lTmp);
342 }
343
344 // 1. calculate the normalization factor
345
346 for (int i = 0; i < fDomain.getIssues().size(); i++) {
347 // 1. calculate the normalization factor
348 double lN = 0;
349 for (int j = 0; j < fEvaluatorHyps.get(i).size(); j++) {
350 EvaluatorHypothesis lHyp = fEvaluatorHyps.get(i).get(j);
351 lN += lHyp.getProbability()
352 * conditionalDistribution(
353 getPartialUtility(lBid, i)
354 + getExpectedWeight(i)
355 * (lHyp.getEvaluator().getEvaluation(
356 fUS, lBid, issues.get(i)
357 .getNumber())),
358 fPreviousBidUtility);
359 }
360 // 2. receiveMessage probabilities
361 for (int j = 0; j < fEvaluatorHyps.get(i).size(); j++) {
362 EvaluatorHypothesis lHyp = fEvaluatorHyps.get(i).get(j);
363 lEvaluatorHyps
364 .get(i)
365 .get(j)
366 .setProbability(
367 lHyp.getProbability()
368 * conditionalDistribution(
369 getPartialUtility(lBid, i)
370 + getExpectedWeight(i)
371 * (lHyp.getEvaluator()
372 .getEvaluation(
373 fUS,
374 lBid,
375 issues.get(
376 i)
377 .getNumber())),
378 fPreviousBidUtility) / lN);
379 }
380 }
381 fEvaluatorHyps = lEvaluatorHyps;
382 // }
383 printEvalsDistribution();
384 }
385
386 public boolean haveSeenBefore(Bid pBid) {
387 for (Bid tmpBid : fBiddingHistory) {
388 if (pBid.equals(tmpBid))
389 return true;
390 }
391 return false;
392 }
393
394 public void updateBeliefs(Bid pBid) throws Exception {
395 if (!isCrashed()) {
396 if (haveSeenBefore(pBid))
397 return;
398 fBiddingHistory.add(pBid);
399
400 // do not receiveMessage the bids if it is the first bid
401 if (fBiddingHistory.size() > 1) {
402
403 // receiveMessage the weights
404 updateWeights();
405 // receiveMessage evaluation functions
406 updateEvaluationFns();
407 } else {
408 // do not receiveMessage the weights
409 // receiveMessage evaluation functions
410 updateEvaluationFns();
411 } // if
412
413 // System.out.println(getMaxHyp().toString());
414 // calculate utility of the next partner's bid according to the
415 // concession functions
416 fPreviousBidUtility = fPreviousBidUtility - 0.003;
417 for (int i = 0; i < fExpectedWeights.length; i++) {
418 fExpectedWeights[i] = getExpectedWeight(i);
419 }
420 findMinMaxUtility();
421 // printBestHyp();
422 }
423 }
424
425 /**
426 * Plan: cache the results for pBid in a Hash table. empty the hash table
427 * whenever updateWeights or updateEvaluationFns is called.
428 *
429 * @param pBid
430 * @return weeighted utility where weights represent likelihood of each
431 * hypothesis
432 * @throws Exception
433 */
434 public double getExpectedUtility(Bid pBid) throws Exception {
435 // calculate expected utility
436 double u = 0;
437 for (int j = 0; j < fDomain.getIssues().size(); j++) {
438 // calculate expected weight of the issue
439 double w = fExpectedWeights[j];
440 /*
441 * for(int k=0;k<fWeightHyps.get(j).size();k++) w +=
442 * fWeightHyps.get(
443 * j).get(k).getProbability()*fWeightHyps.get(j).get(
444 * k).getWeight();(
445 */
446 u = u + w * getExpectedEvaluationValue(pBid, j);
447 }
448
449 return u;
450 }
451
452 private void printBestHyp() {
453 double[] lBestWeights = new double[fUS.getDomain().getIssues().size()];
454 EvaluatorHypothesis[] lBestEvals = new EvaluatorHypothesis[fUS
455 .getDomain().getIssues().size()];
456 for (int i = 0; i < fUS.getDomain().getIssues().size(); i++) {
457 // find best weight
458 double lMaxWeightProb = -1;
459 for (int j = 0; j < fWeightHyps.get(i).size(); j++) {
460 if (fWeightHyps.get(i).get(j).getProbability() > lMaxWeightProb) {
461 lMaxWeightProb = fWeightHyps.get(i).get(j).getProbability();
462 lBestWeights[i] = fWeightHyps.get(i).get(j).getWeight();
463 }
464 }
465 // find best evaluation fn
466 double lMaxEvalProb = -1;
467 for (int j = 0; j < fEvaluatorHyps.get(i).size(); j++) {
468 if (fEvaluatorHyps.get(i).get(j).getProbability() > lMaxEvalProb) {
469 lMaxEvalProb = fEvaluatorHyps.get(i).get(j)
470 .getProbability();
471 lBestEvals[i] = fEvaluatorHyps.get(i).get(j);
472 }
473 }
474
475 }
476 /*
477 * //print all weights for(int
478 * i=0;i<fUS.getDomain().getIssues().size();i++) {
479 * System.out.print(String.format("%1.2f", getExpectedWeight(i))+";"); }
480 * //print all Evaluators for(int
481 * i=0;i<fUS.getDomain().getIssues().size();i++) {
482 * System.out.print(lBestEvals[i].getDesc()+";"); }
483 * System.out.println();
484 */
485 }
486
487 void printEvalsDistribution() {
488 /*
489 * for(int i=0;i<fUS.getDomain().getIssues().size();i++) { for(int
490 * j=0;j<fEvaluatorHyps.get(i).size();j++)
491 * System.out.print(String.format("%1.2f",
492 * fEvaluatorHyps.get(i).get(j).getProbability())+";");
493 * System.out.println(); }
494 */
495
496 }
497
498 public double getNormalizedWeight(Issue i, int startingNumber) {
499 double sum = 0;
500 for (Issue issue : fDomain.getIssues()) {
501 sum += getExpectedWeight(issue.getNumber() - startingNumber);
502 }
503 return (getExpectedWeight(i.getNumber() - startingNumber)) / sum;
504 }
505
506}
Note: See TracBrowser for help on using the repository browser.