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 int check_xy_exists(int x, int y, bimap *bm)
 161 {
 162         int res = 0;
 163         if (getxy(x, y, bm->f) != NULL) res = 1;
 164         return res;
 165 }
 166
 167 int check_space(int x, int y, direction d, int delta, bimap *bm)
 168 {
 169         switch(d){
 170         case LEFT: x = x - delta; break;
 171         case UP: y = y - delta; break;
 172         case RIGHT: x = x + delta; break;
 173         case DOWN: y = y + delta; break;
 174         }
 175         return check_xy_exists(x, y, bm);
 176 }
 177
 178 /*
 179  * Each coordinate has three related boolean variables. The combination of those boolean variables
 180  * defines tiles:
 181  * 000: Wall
 182  * 001: Free
 183  * 010: Box
 184  * 100: Box on target
 185  * 011: Target
 186  * 101: Agent
 187  * 110: Agent on target
 188  * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
 189  * tiles in the shrinked screen.
 190  * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
 191  * directly in transition relations.
 192  */
 193
 194 state *encode_screen(sokoban_screen *screen)
 195 {
 196         LACE_ME;
 197
 198         BDDVAR vars[HASH_COUNT(screen) * 3];
 199         for (uint8_t i = 0; i < HASH_COUNT(screen) * 3; i++){
 200                 vars[i] = i * 2;
 201         }
 202
 203         uint8_t st_enc[HASH_COUNT(screen) * 3];
 204
 205         BDDSET varset = sylvan_set_fromarray(vars, HASH_COUNT(screen) * 3);
 206         BDD s;
 207         state *fullState = NULL;
 208         fullState = (state *)malloc(sizeof(state));
 209         fullState->vars.varset = varset;
 210         fullState->vars.size = HASH_COUNT(screen) * 3;
 211         int tile_index = 0;
 212         sokoban_screen *r;
 213         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
 214                 switch(r->tile){
 215                 case FREE: //001
 216                         st_enc[tile_index] = 0;
 217                         tile_index++;
 218                         st_enc[tile_index] = 0;
 219                         tile_index++;
 220                         st_enc[tile_index] = 1;
 221                         tile_index++;
 222                         break;
 223                 case WALL: //000
 224                         st_enc[tile_index] = 0;
 225                         tile_index++;
 226                         st_enc[tile_index] = 0;
 227                         tile_index++;
 228                         st_enc[tile_index] = 0;
 229                         tile_index++;
 230                         break;
 231                 case BOX: //010
 232                         st_enc[tile_index] = 0;
 233                         tile_index++;
 234                         st_enc[tile_index] = 1;
 235                         tile_index++;
 236                         st_enc[tile_index] = 0;
 237                         tile_index++;
 238                         break;
 239                 case TARGET: //011
 240                         st_enc[tile_index] = 0;
 241                         tile_index++;
 242                         st_enc[tile_index] = 1;
 243                         tile_index++;
 244                         st_enc[tile_index] = 1;
 245                         tile_index++;
 246                         break;
 247                 case AGENT: //101
 248                         st_enc[tile_index] = 1;
 249                         tile_index++;
 250                         st_enc[tile_index] = 0;
 251                         tile_index++;
 252                         st_enc[tile_index] = 1;
 253                         tile_index++;
 254                         break;
 255                 case TARGAGENT: //110
 256                         st_enc[tile_index] = 1;
 257                         tile_index++;
 258                         st_enc[tile_index] = 1;
 259                         tile_index++;
 260                         st_enc[tile_index] = 0;
 261                         tile_index++;
 262                         break;
 263                 case TARGBOX: //100
 264                         st_enc[tile_index] = 1;
 265                         tile_index++;
 266                         st_enc[tile_index] = 0;
 267                         tile_index++;
 268                         st_enc[tile_index] = 0;
 269                         tile_index++;
 270                         break;
 271                 }
 272         }
 273         s = sylvan_cube(varset, st_enc);
 274         fullState->bdd = s;
 275         printf("Initial state encoded\n");
 276         return fullState;
 277 }
 278
 279 int
 280 test_relprod()
 281 {
 282     LACE_ME;
 283
 284     BDDVAR vars[] = {0,2,4};
 285     BDDVAR all_vars[] = {4,5};
 286
 287     BDDSET vars_set = sylvan_set_fromarray(vars, 3);
 288     BDDSET all_vars_set = sylvan_set_fromarray(all_vars, 2);
 289
 290     BDD s, t, next, prev;
 291     BDD zeroes, ones;
 292
 293     // transition relation: 000 --> 111 and !000 --> 000
 294     t = sylvan_false;
 295     //t = sylvan_union_cube(t, all_vars_set, ((uint8_t[]){0,1,0,1,0,1}));
 296     //t = sylvan_union_cube(t, all_vars_set, ((uint8_t[]){1,0,2,0,2,0}));
 297     //t = sylvan_union_cube(t, all_vars_set, ((uint8_t[]){2,0,1,0,2,0}));
 298     t = sylvan_union_cube(t, all_vars_set, ((uint8_t[]){1,0}));
 299
 300     s = sylvan_cube(vars_set, (uint8_t[]){0,0,1});
 301     zeroes = sylvan_cube(vars_set, (uint8_t[]){0,0,0});
 302     ones = sylvan_cube(vars_set, (uint8_t[]){0,0,1});
 303
 304     next = sylvan_relnext(s, t, all_vars_set);
 305     prev = sylvan_relprev(t, next, all_vars_set);
 306     if (next == zeroes) printf("Pass 1\n");
 307     if (prev == ones || prev == zeroes) printf("Pass 2\n");
 308
 309     return 0;
 310 }
 311
 312 BDD encode_rel(sokoban_screen *screen)
 313 {
 314         LACE_ME;
 315         //      int tile_count = 0;
 316         BDD t = sylvan_false;
 317         //BDDVAR relvars[];
 318         //BDDSET relvarset;
 319         //uint8_t rel_enc[];
 320
 321         bimap *bm = create_bimap_helper(screen);
 322         int x = 0;
 323         int y = 0;
 324         bddvar_xy_map *bddxy = NULL;
 325
 326         //left relation
 327         for (unsigned int i = 0; i < HASH_COUNT(screen); i++){
 328                 printf("i:%d\n", i);
 329                 bddxy = getbdd(i*3, bm->t);
 330                 x = bddxy->value.x;
 331                 y = bddxy->value.y;
 332                 if (check_space(x, y, LEFT, 1, bm) == 0){
 333                         sokoban_screen *tmp_scr = get_coord(x, y, screen);
 334                         if (tmp_scr->tile == AGENT){
 335                                 //1 1 0 0 1 1 (1 0 1 -> 1 0 1)
 336                                 BDDVAR relvars[6]  = {i * 3, i * 3 + 1, i * 3 + 2, i * 3 + 3, i * 3 + 4, i * 3 + 5};
 337                                 BDDSET relvarset = sylvan_set_fromarray(relvars, 6);
 338                                 uint8_t rel_enc[6] = {1, 1, 0, 0, 1, 1};
 339                                 t = sylvan_union_cube(t, relvarset, rel_enc);
 340                         }
 341                         if (tmp_scr->tile == TARGAGENT){
 342                                 //1 1 1 1 0 0 (1 1 0 -> 1 1 0)
 343                                 BDDVAR relvars[6]  = {i * 3, i * 3 + 1, i * 3 + 2, i * 3 + 3, i * 3 + 4, i * 3 + 5};
 344                                 BDDSET relvarset = sylvan_set_fromarray(relvars, 6);
 345                                 uint8_t rel_enc[6] = {1, 1, 1, 1, 0, 0};
 346                                 t = sylvan_union_cube(t, relvarset, rel_enc);
 347                         }
 348                 }
 349                 else if (check_space(x, y, LEFT, 1, bm) == 1 && check_space(x, y, LEFT, 2, bm) == 0){
 350                         sokoban_screen *tmp_scr = get_coord(x, y, screen);
 351                         sokoban_screen *tmp_scr_d = get_coord(x - 1, y, screen);
 352                         xy_bddvar_map *bddvar = getxy(x - 1, y, bm->f);
 353                         int deltai = bddvar->value.var[0];
 354                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == FREE){
 355                                 //(0 1 0 0 1 1 1 0 0 0 1 1)
 356                                 BDDVAR relvars[12]  = {deltai*3, deltai*3+1, deltai*3+2, deltai*3+3, deltai*3+4, deltai*3+5, i*3, i*3+1, i*3+2, i*3+3, i*3+4, i*3+5};
 357                                 BDDSET relvarset = sylvan_set_fromarray(relvars, 12);
 358                                 uint8_t rel_enc[12] = {0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1};
 359                                 t = sylvan_union_cube(t, relvarset, rel_enc);
 360                         }
 361                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == TARGET){
 362                                 //(0 1 1 0 1 1 1 0 0 1 1 1)
 363                                 BDDVAR relvars[12]  = {deltai*3, deltai*3+1, deltai*3+2, deltai*3+3, deltai*3+4, deltai*3+5, i*3, i*3+1, i*3+2, i*3+3, i*3+4, i*3+5};
 364                                 BDDSET relvarset = sylvan_set_fromarray(relvars, 12);
 365                                 uint8_t rel_enc[12] = {0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1};
 366                                 t = sylvan_union_cube(t, relvarset, rel_enc);
 367                         }
 368                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == FREE){
 369                                 //(0 1 0 1 1 0 1 0 1 0 0 1)
 370                                 BDDVAR relvars[12]  = {deltai*3, deltai*3+1, deltai*3+2, deltai*3+3, deltai*3+4, deltai*3+5, i*3, i*3+1, i*3+2, i*3+3, i*3+4, i*3+5};
 371                                 BDDSET relvarset = sylvan_set_fromarray(relvars, 12);
 372                                 uint8_t rel_enc[12] = {0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1};
 373                                 t = sylvan_union_cube(t, relvarset, rel_enc);
 374                         }
 375                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == TARGET){
 376                                 //(0 1 1 1 1 0 1 0 1 1 0 1)
 377                                 BDDVAR relvars[12]  = {deltai*3, deltai*3+1, deltai*3+2, deltai*3+3, deltai*3+4, deltai*3+5, i*3, i*3+1, i*3+2, i*3+3, i*3+4, i*3+5};
 378                                 BDDSET relvarset = sylvan_set_fromarray(relvars, 12);
 379                                 uint8_t rel_enc[12] = {0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1};
 380                                 t = sylvan_union_cube(t, relvarset, rel_enc);
 381                         }
 382                         if (tmp_scr->tile == AGENT && (tmp_scr_d->tile == BOX || tmp_scr_d->tile == TARGBOX)){
 383                                 //can't move
 384                         }
 385                         if (tmp_scr->tile == TARGAGENT && (tmp_scr_d->tile == BOX || tmp_scr_d->tile == TARGBOX)){
 386                                 //can't move
 387                         }
 388                 }
 389                 else if (check_space(x, y, LEFT, 1, bm) == 1 && check_space(x, y, LEFT, 2, bm) == 1){
 390                         sokoban_screen *tmp_scr = get_coord(x, y, screen);
 391                         sokoban_screen *tmp_scr_d = get_coord(x - 1, y, screen);
 392                         sokoban_screen *tmp_scr_g = get_coord(x - 2, y, screen);
 393                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == FREE){
 394                                 //can move
 395                         }
 396                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == TARGET){
 397                                 //can move
 398                         }
 399                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == FREE){
 400                                 //can move
 401                         }
 402                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == TARGET){
 403                                 //can move
 404                         }
 405                         if (tmp_scr->tile == AGENT && tmp_scr_d-> tile == BOX && (tmp_scr_g->tile == BOX || tmp_scr_g->tile == TARGBOX)){
 406                                 //can't move
 407                         }
 408                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d-> tile == BOX && (tmp_scr_g->tile == BOX || tmp_scr_g->tile == TARGBOX)){
 409                                 //can't move
 410                         }
 411                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == BOX && tmp_scr_g->tile == FREE){
 412                                 //can move
 413                         }
 414                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == TARGBOX && tmp_scr_g->tile == FREE){
 415                                 //can move
 416                         }
 417                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == BOX && tmp_scr_g->tile == TARGET){
 418                                 //can move
 419                         }
 420                         if (tmp_scr->tile == AGENT && tmp_scr_d->tile == TARGBOX && tmp_scr_g->tile == TARGET){
 421                                 //can move
 422                         }
 423                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == BOX && tmp_scr_g->tile == FREE){
 424                                 //can move
 425                         }
 426                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == TARGBOX && tmp_scr_g->tile == FREE){
 427                                 //can move
 428                         }
 429                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == BOX && tmp_scr_g->tile == TARGET){
 430                                 //can move
 431                         }
 432                         if (tmp_scr->tile == TARGAGENT && tmp_scr_d->tile == TARGBOX && tmp_scr_g->tile == TARGET){
 433                                 //can move
 434                         }
 435                 }
 436                 printf("x:%d y:%d\n", x, y);
 437         }
 438
 439         //up relation
 440
 441         //right relation
 442
 443         //down relation
 444
 445         return sylvan_true;
 446 }