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