modelchecker/coord.c

   1 #include <argp.h>
   2 #include <inttypes.h>
   3 #include <locale.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <sys/time.h>
   8
   9 #ifdef HAVE_PROFILER
  10 #include <gperftools/profiler.h>
  11 #endif
  12
  13 #include <sylvan.h>
  14 #include <llmsset.h>
  15 #include <lace.h>
  16
  17 #include "coord.h"
  18 #include "sokoban.h"
  19
  20 /*
  21  * Global TODOs for now:
  22  * - update the helper maps so it is a single bimap
  23  * - make a data structure for relations
  24  * - encode relations as a set of four relations for each move
  25  */
  26
  27 typedef struct {
  28         int x;
  29         int y;
  30 } xy;
  31
  32 typedef struct {
  33         int var[3];
  34 } bddvar;
  35
  36 typedef struct {
  37         xy key;
  38         bddvar value;
  39         UT_hash_handle hh;
  40 } xy_bddvar_map;
  41
  42 typedef struct {
  43         int key;
  44         xy value;
  45         UT_hash_handle hh;
  46 } bddvar_xy_map;
  47
  48 typedef struct {
  49         xy_bddvar_map *f;
  50         bddvar_xy_map *t;
  51 } bimap;
  52
  53 xy_bddvar_map *getxy(int x, int y, xy_bddvar_map *map)
  54 {
  55         xy_bddvar_map k, *r = NULL;
  56         memset(&k, 0, sizeof(xy_bddvar_map));
  57         k.key.x = x;
  58         k.key.y = y;
  59         HASH_FIND(hh, map, &k.key, sizeof(xy), r);
  60         return r;
  61 }
  62
  63 bddvar_xy_map *getbdd(int key, bddvar_xy_map *map)
  64 {
  65         bddvar_xy_map k, *r = NULL;
  66         memset(&k, 0, sizeof(bddvar_xy_map));
  67         k.key = key;
  68         HASH_FIND(hh, map, &k.key, sizeof(int), r);
  69         return r;
  70 }
  71
  72 xy_bddvar_map *create_xy_bddvar_map(sokoban_screen *screen)
  73 {
  74         int varcount = 0;
  75         sokoban_screen *r;
  76         xy_bddvar_map *xybdd = NULL;
  77         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
  78                 xy_bddvar_map *f = NULL;
  79                 //bddvar_xy_map *t = NULL;
  80
  81                 f = (xy_bddvar_map *)malloc(sizeof(xy_bddvar_map));
  82                 memset(f, 0, sizeof(xy_bddvar_map));
  83                 f->key.x = r->coord.x;
  84                 f->key.y = r->coord.y;
  85                 f->value.var[0] = varcount;
  86                 f->value.var[1] = varcount + 1;
  87                 f->value.var[2] = varcount + 2;
  88                 HASH_ADD(hh, xybdd, key, sizeof(xy), f);
  89                 varcount = varcount + 3;
  90         }
  91         return xybdd;
  92 }
  93
  94 bddvar_xy_map *create_bddvar_xy_map(sokoban_screen *screen)
  95 {
  96         int varcount = 0;
  97         sokoban_screen *r;
  98         bddvar_xy_map *bddxy = NULL;
  99         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
 100                 for (int i = 0; i <3; i++){
 101                         bddvar_xy_map *f = NULL;
 102                         //bddvar_xy_map *t = NULL;
 103
 104                         f = (bddvar_xy_map *)malloc(sizeof(bddvar_xy_map));
 105                         memset(f, 0, sizeof(bddvar_xy_map));
 106                         f->key = varcount + i;
 107                         f->value.x = r->coord.x;
 108                         f->value.y = r->coord.y;
 109                         HASH_ADD(hh, bddxy, key, sizeof(int), f);
 110                 }
 111                 varcount = varcount + 3;
 112         }
 113         return bddxy;
 114 }
 115
 116 bimap *create_bimap_helper(sokoban_screen *screen)
 117 {
 118         int varcount = 0;
 119         sokoban_screen *r;
 120         xy_bddvar_map *xybdd = NULL;
 121         bddvar_xy_map *bddxy = NULL;
 122         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
 123                 xy_bddvar_map *f = NULL;
 124                 f = (xy_bddvar_map *)malloc(sizeof(xy_bddvar_map));
 125                 memset(f, 0, sizeof(xy_bddvar_map));
 126                 f->key.x = r->coord.x;
 127                 f->key.y = r->coord.y;
 128                 f->value.var[0] = varcount;
 129                 f->value.var[1] = varcount + 1;
 130                 f->value.var[2] = varcount + 2;
 131                 HASH_ADD(hh, xybdd, key, sizeof(xy), f);
 132
 133                 for (int i = 0; i <3; i++){
 134                         bddvar_xy_map *t = NULL;
 135                         t = (bddvar_xy_map *)malloc(sizeof(bddvar_xy_map));
 136                         memset(t, 0, sizeof(bddvar_xy_map));
 137                         t->key = varcount + i;
 138                         t->value.x = r->coord.x;
 139                         t->value.y = r->coord.y;
 140                         HASH_ADD(hh, bddxy, key, sizeof(int), t);
 141                 }
 142                 varcount = varcount + 3;
 143         }
 144         bimap *bm = NULL;
 145         bm = (bimap *)malloc(sizeof(bimap));
 146         bm->f = xybdd;
 147         bm->t = bddxy;
 148         return bm;
 149 }
 150
 151 /*
 152  * Each coordinate has three related boolean variables. The combination of those boolean variables
 153  * defines tiles:
 154  * 000: Wall
 155  * 001: Free
 156  * 010: Box
 157  * 100: Box on target
 158  * 011: Target
 159  * 101: Agent
 160  * 110: Agent on target
 161  * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
 162  * tiles in the shrinked screen.
 163  * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
 164  * directly in transition relations.
 165  */
 166
 167 BDD encode_screen(sokoban_screen *screen)
 168 {
 169         BDD state = sylvan_false;
 170         int tile_index = 0;
 171         sokoban_screen *r;
 172         LACE_ME;
 173         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
 174                 switch(r->tile){
 175                 case FREE:
 176                         if (state == sylvan_false){
 177                                 state = sylvan_not(sylvan_ithvar(tile_index));
 178                                 tile_index++;
 179                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 180                                 tile_index++;
 181                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 182                                 tile_index++;
 183                         }
 184                         else {
 185                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 186                                 tile_index++;
 187                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 188                                 tile_index++;
 189                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 190                                 tile_index++;
 191                         }
 192                         break;
 193                 case WALL:
 194                         if (state == sylvan_false){
 195                                 state = sylvan_not(sylvan_ithvar(tile_index));
 196                                 tile_index++;
 197                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 198                                 tile_index++;
 199                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 200                                 tile_index++;
 201                         }
 202                         else {
 203                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 204                                 tile_index++;
 205                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 206                                 tile_index++;
 207                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 208                                 tile_index++;
 209                         }
 210                         break;
 211                 case BOX:
 212                         if (state == sylvan_false){
 213                                 state = sylvan_not(sylvan_ithvar(tile_index));
 214                                 tile_index++;
 215                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 216                                 tile_index++;
 217                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 218                                 tile_index++;
 219                         }
 220                         else {
 221                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 222                                 tile_index++;
 223                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 224                                 tile_index++;
 225                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 226                                 tile_index++;
 227                         }
 228                         break;
 229                 case TARGET:
 230                         if (state == sylvan_false){
 231                                 state = sylvan_not(sylvan_ithvar(tile_index));
 232                                 tile_index++;
 233                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 234                                 tile_index++;
 235                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 236                                 tile_index++;
 237                         }
 238                         else {
 239                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 240                                 tile_index++;
 241                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 242                                 tile_index++;
 243                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 244                                 tile_index++;
 245                         }
 246                         break;
 247                 case AGENT:
 248                         if (state == sylvan_false){
 249                                 state = sylvan_ithvar(tile_index);
 250                                 tile_index++;
 251                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 252                                 tile_index++;
 253                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 254                                 tile_index++;
 255                         }
 256                         else {
 257                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 258                                 tile_index++;
 259                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 260                                 tile_index++;
 261                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 262                                 tile_index++;
 263                         }
 264                         break;
 265                 case TARGAGENT:
 266                         if (state == sylvan_false){
 267                                 state = sylvan_ithvar(tile_index);
 268                                 tile_index++;
 269                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 270                                 tile_index++;
 271                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 272                                 tile_index++;
 273                         }
 274                         else {
 275                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 276                                 tile_index++;
 277                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 278                                 tile_index++;
 279                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 280                                 tile_index++;
 281                         }
 282                         break;
 283                 case TARGBOX:
 284                         if (state == sylvan_false){
 285                                 state = sylvan_ithvar(tile_index);
 286                                 tile_index++;
 287                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 288                                 tile_index++;
 289                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 290                                 tile_index++;
 291                         }
 292                         else {
 293                                 state = sylvan_and(state, sylvan_ithvar(tile_index));
 294                                 tile_index++;
 295                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 296                                 tile_index++;
 297                                 state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
 298                                 tile_index++;
 299                         }
 300                         break;
 301                 }
 302         }
 303         /*
 304         xy_bddvar_map *map = NULL;
 305         map = create_xy_bddvar_map(screen);
 306         xy_bddvar_map *m = getxy(1, 1, map);
 307         bddvar_xy_map *map2 = NULL;
 308         map2 = create_bddvar_xy_map(screen);
 309         bddvar_xy_map *m2 = getbdd(2, map2);
 310         printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
 311         printf("Test2: %d %d\n", m2->value.x, m2->value.y);
 312         */
 313         /*
 314         bimap *bm = NULL;
 315         bm = create_bimap_helper(screen);
 316         xy_bddvar_map *m = getxy(1, 1, bm->f);
 317         bddvar_xy_map *m2 = getbdd(2, bm->t);
 318         printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
 319         printf("Test2: %d %d\n", m2->value.x, m2->value.y);
 320         printf("%d tiles were encoded\n", tile_index);
 321         if (bm != NULL) printf ("WORKS!\n");
 322         */
 323         return state;
 324 }
 325
 326 BDD encode_rel(sokoban_screen *screen)
 327 {
 328         int num_tiles;
 329         num_tiles = HASH_COUNT(screen);
 330         printf("Number of tiles: %d\n", num_tiles);
 331         return sylvan_true;
 332 }
 333
 334 void test()
 335 {
 336
 337         printf("Test!\n");
 338         BDD a = sylvan_true;
 339         BDD b = sylvan_not(a);
 340         if (b == sylvan_false){
 341                 printf("BDD works!\n");
 342         } else {
 343                 printf("BDD does not work!\n");
 344         }
 345         LACE_ME;
 346         BDD c = sylvan_ithvar(1);
 347         if (sylvan_high(c) == sylvan_true && sylvan_low(c) == sylvan_false) printf("VAR works 1\n");
 348         if (sylvan_var(c) == 1) printf("Var works 2\n");
 349 }