transitions.py 23 KB
Newer Older
1
2
3
4
5
6
"""
The transitions module defines the base Transitions class and a
derived GridTransitions class, which allows for the specification of
possible transitions over a 2D grid.
"""

7
8
import numpy as np

9
10
11

class Transitions:
    """
12
13
    Base Transitions class.

14
15
16
17
18
    Generic class that implements checks to control whether a
    certain transition is allowed (agent facing a direction
    `orientation' and moving into direction `direction')
    """

19
    def get_transitions(self, cell_transition, orientation):
20
21
22
23
24
25
        """
        Return a tuple of transitions available in a cell specified by
        `cell_transition' for an agent facing direction `orientation'
        (e.g., a tuple of size of the maximum number of transitions,
        with values 0 or 1, or potentially in between,
        for stochastic transitions).
26
27
28
29

        Parameters
        ----------
        cell_transition : [cell content]
spiglerg's avatar
spiglerg committed
30
            The object is specific to each derived class (e.g., for
31
32
33
34
35
36
37
38
39
40
            GridTransitions, int), and is only manipulated by methods
            of the Transitions derived classes.
        orientation : int
            Orientation of the agent inside the cell.

        Returns
        -------
        tuple
            List of the validity of transitions in the cell.

41
42
43
        """
        raise NotImplementedError()

44
    def set_transitions(self, cell_transition, orientation, new_transitions):
45
46
47
48
49
        """
        Return a `cell_transition' specification where the transitions
        available for an agent facing direction `orientation' are replaced
        with the tuple `new_transitions'. `new_orientations' must have
        one element for each possible transition.
50
51
52
53

        Parameters
        ----------
        cell_transition : [cell-content]
spiglerg's avatar
spiglerg committed
54
            The object is specific to each derived class (e.g., for
55
56
57
58
59
60
61
62
63
64
65
66
67
68
            GridTransitions, int), and is only manipulated by methods
            of the Transitions derived classes.
        orientation : int
            Orientation of the agent inside the cell.
        new_transitions : tuple
            Tuple of new transitions validitiy for the cell.

        Returns
        -------
        [cell-content]
            An updated class-specific object that replaces the original
            transitions validity of `cell_transition' with `new_transitions',
            for the appropriate `orientation'.

69
70
71
        """
        raise NotImplementedError()

72
    def get_transition(self, cell_transition, orientation, direction):
73
74
75
76
77
        """
        Return the status of whether an agent oriented in directions
        `orientation' and inside a cell with transitions `cell_transition'
        can move to the cell in direction `direction' relative
        to the current cell.
78
79
80
81

        Parameters
        ----------
        cell_transition : [cell-content]
spiglerg's avatar
spiglerg committed
82
            The object is specific to each derived class (e.g., for
83
84
85
86
87
88
89
90
91
92
93
94
95
            GridTransitions, int), and is only manipulated by methods
            of the Transitions derived classes.
        orientation : int
            Orientation of the agent inside the cell.
        direction : int
            Direction of movement whose validity is to be tested.

        Returns
        -------
        int or float (depending on derived class)
            Validity of the requested transition (e.g.,
            0/1 allowed/not allowed, a probability in [0,1], etc...)

96
97
98
        """
        raise NotImplementedError()

99
100
    def set_transition(self, cell_transition, orientation, direction,
                       new_transition):
101
102
103
104
105
106
        """
        Return a `cell_transition' specification where the status of
        whether an agent oriented in direction `orientation' and inside
        a cell with transitions `cell_transition' can move to the cell
        in direction `direction' relative to the current cell is set
        to `new_transition'.
107
108
109
110

        Parameters
        ----------
        cell_transition : [cell-content]
spiglerg's avatar
spiglerg committed
111
            The object is specific to each derived class (e.g., for
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
            GridTransitions, int), and is only manipulated by methods
            of the Transitions derived classes.
        orientation : int
            Orientation of the agent inside the cell.
        direction : int
            Direction of movement whose validity is to be tested.
        new_transition : int or float (depending on derived class)
            Validity of the requested transition (e.g.,
            0/1 allowed/not allowed, a probability in [0,1], etc...)

        Returns
        -------
        [cell-content]
            An updated class-specific object that replaces the original
            transitions validity of `cell_transition' with `new_transitions',
            for the appropriate `orientation' to `direction'.

129
130
131
132
        """
        raise NotImplementedError()


133
class Grid4Transitions(Transitions):
134
    """
135
    Grid4Transitions class derived from Transitions.
136

137
138
    Special case of `Transitions' over a 2D-grid (FlatLand).
    Transitions are possible to neighboring cells on the grid if allowed.
139
    GridTransitions keeps track of valid transitions supplied as `transitions'
140
    list, each represented as a bitmap of 16 bits.
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

    Whether a transition is allowed or not depends on which direction an agent
    inside the cell is facing (0=North, 1=East, 2=South, 3=West) and which
    direction the agent wants to move to
    (North, East, South, West, relative to the cell).
    Each transition (orientation, direction)
    can be allowed (1) or forbidden (0).

    For example, in case of no diagonal transitions on the grid, the 16 bits
    of the transition bitmaps are organized in 4 blocks of 4 bits each, the
    direction that the agent is facing.
    E.g., the most-significant 4-bits represent the possible movements (NESW)
    if the agent is facing North, etc...

    agent's direction:          North    East   South   West
    agent's allowed movements:  [nesw]   [nesw] [nesw]  [nesw]
157
    example:                     1000     0000   0010    0000
158
159

    In the example, the agent can move from North to South and viceversa.
160
161
    """

162
    def __init__(self, transitions):
163
        self.transitions = transitions
164
165
166
167
168
        self.sDirs = "NESW"
        self.lsDirs = list(self.sDirs)

        # row,col delta for each direction
        self.gDir2dRC = np.array([[-1, 0], [0, 1], [1, 0], [0, -1]])
169

170
    def get_transitions(self, cell_transition, orientation):
171
172
173
174
175
        """
        Get the 4 possible transitions ((N,E,S,W), 4 elements tuple
        if no diagonal transitions allowed) available for an agent oriented
        in direction `orientation' and inside a cell with
        transitions `cell_transition'.
176
177
178
179

        Parameters
        ----------
        cell_transition : int
180
            16 bits used to encode the valid transitions for a cell.
181
182
183
184
185
186
187
188
        orientation : int
            Orientation of the agent inside the cell.

        Returns
        -------
        tuple
            List of the validity of transitions in the cell.

189
        """
spiglerg's avatar
spiglerg committed
190
        bits = (cell_transition >> ((3 - orientation) * 4))
191
        return ((bits >> 3) & 1, (bits >> 2) & 1, (bits >> 1) & 1, (bits) & 1)
192

193
    def set_transitions(self, cell_transition, orientation, new_transitions):
194
195
196
197
198
199
        """
        Set the possible transitions (e.g., (N,E,S,W), 4 elements tuple
        if no diagonal transitions allowed) available for an agent
        oriented in direction `orientation' and inside a cell with transitions
        `cell_transition'. A new `cell_transition' is returned with
        the specified bits replaced by `new_transitions'.
200
201
202
203

        Parameters
        ----------
        cell_transition : int
204
            16 bits used to encode the valid transitions for a cell.
205
206
207
208
209
210
211
212
213
214
215
216
        orientation : int
            Orientation of the agent inside the cell.
        new_transitions : tuple
            Tuple of new transitions validitiy for the cell.

        Returns
        -------
        int
            An updated bitmap that replaces the original transitions validity
            of `cell_transition' with `new_transitions', for the appropriate
            `orientation'.

217
        """
spiglerg's avatar
spiglerg committed
218
        mask = (1 << ((4 - orientation) * 4)) - (1 << ((3 - orientation) * 4))
219
220
221
222
223
224
225
        negmask = ~mask

        new_transitions = \
            (new_transitions[0] & 1) << 3 | \
            (new_transitions[1] & 1) << 2 | \
            (new_transitions[2] & 1) << 1 | \
            (new_transitions[3] & 1)
226
        # new_transitions = np.packbits((0, 0, 0, 0) + new_transitions)  # alternative
227

spiglerg's avatar
spiglerg committed
228
        cell_transition = (cell_transition & negmask) | (new_transitions << ((3 - orientation) * 4))
229
230
231

        return cell_transition

232
    def get_transition(self, cell_transition, orientation, direction):
233
234
235
236
237
        """
        Get the transition bit (1 value) that determines whether an agent
        oriented in direction `orientation' and inside a cell with transitions
        `cell_transition' can move to the cell in direction `direction'
        relative to the current cell.
238
239
240
241

        Parameters
        ----------
        cell_transition : int
242
            16 bits used to encode the valid transitions for a cell.
243
244
245
246
247
248
249
250
251
252
        orientation : int
            Orientation of the agent inside the cell.
        direction : int
            Direction of movement whose validity is to be tested.

        Returns
        -------
        int
            Validity of the requested transition: 0/1 allowed/not allowed.

253
        """
spiglerg's avatar
spiglerg committed
254
        return ((cell_transition >> ((4 - 1 - orientation) * 4)) >> (4 - 1 - direction)) & 1
255

256
    def set_transition(self, cell_transition, orientation, direction, new_transition, remove_deadends=False):
257
258
259
260
261
        """
        Set the transition bit (1 value) that determines whether an agent
        oriented in direction `orientation' and inside a cell with transitions
        `cell_transition' can move to the cell in direction `direction'
        relative to the current cell.
262
263
264
265

        Parameters
        ----------
        cell_transition : int
266
            16 bits used to encode the valid transitions for a cell.
267
268
269
270
271
272
        orientation : int
            Orientation of the agent inside the cell.
        direction : int
            Direction of movement whose validity is to be tested.
        new_transition : int
            Validity of the requested transition: 0/1 allowed/not allowed.
273
274
        remove_deadends -- boolean, default False
            remove all deadend transitions.
275
276
277
278
279
280
281
        Returns
        -------
        int
            An updated bitmap that replaces the original transitions validity
            of `cell_transition' with `new_transitions', for the appropriate
            `orientation'.

282
283
        """
        if new_transition:
spiglerg's avatar
spiglerg committed
284
            cell_transition |= (1 << ((4 - 1 - orientation) * 4 + (4 - 1 - direction)))
285
        else:
spiglerg's avatar
spiglerg committed
286
            cell_transition &= ~(1 << ((4 - 1 - orientation) * 4 + (4 - 1 - direction)))
287

288
289
290
        if remove_deadends:
            cell_transition = self.remove_deadends(cell_transition)

291
292
293
294
        return cell_transition

    def rotate_transition(self, cell_transition, rotation=0):
        """
295
296
        Clockwise-rotate a 16-bit transition bitmap by
        rotation={0, 90, 180, 270} degrees.
spiglerg's avatar
spiglerg committed
297
298
299
300

        Parameters
        ----------
        cell_transition : int
301
            16 bits used to encode the valid transitions for a cell.
spiglerg's avatar
spiglerg committed
302
303
        rotation : int
            Angle by which to clock-wise rotate the transition bits in
304
            `cell_transition' by. I.e., rotation={0, 90, 180, 270} degrees.
spiglerg's avatar
spiglerg committed
305
306
307
308
309
310
311

        Returns
        -------
        int
            An updated bitmap that replaces the original transitions bits
            with the equivalent bitmap after rotation.

312
        """
313
314
315
316
317
        # Rotate the individual bits in each block
        value = cell_transition
        rotation = rotation // 90
        for i in range(4):
            block_tuple = self.get_transitions(value, i)
spiglerg's avatar
spiglerg committed
318
            block_tuple = block_tuple[(4 - rotation):] + block_tuple[:(4 - rotation)]
319
320
321
            value = self.set_transitions(value, i, block_tuple)

        # Rotate the 4-bits blocks
spiglerg's avatar
spiglerg committed
322
        value = ((value & (2**(rotation * 4) - 1)) << ((4 - rotation) * 4)) | (value >> (rotation * 4))
323
324
325
326
327
328
329
330

        cell_transition = value
        return cell_transition


class Grid8Transitions(Transitions):
    """
    Grid8Transitions class derived from Transitions.
331

332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
    Special case of `Transitions' over a 2D-grid (FlatLand).
    Transitions are possible to neighboring cells on the grid if allowed.
    GridTransitions keeps track of valid transitions supplied as `transitions'
    list, each represented as a bitmap of 64 bits.

    0=North, 1=North-East, etc.

    """

    def __init__(self, transitions):
        self.transitions = transitions

    def get_transitions(self, cell_transition, orientation):
        """
        Get the 8 possible transitions.

        Parameters
        ----------
        cell_transition : int
            64 bits used to encode the valid transitions for a cell.
        orientation : int
            Orientation of the agent inside the cell.

        Returns
        -------
        tuple
            List of the validity of transitions in the cell.

        """
spiglerg's avatar
spiglerg committed
361
        bits = (cell_transition >> ((7 - orientation) * 8))
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
        cell_transition = (
            (bits >> 7) & 1,
            (bits >> 6) & 1,
            (bits >> 5) & 1,
            (bits >> 4) & 1,
            (bits >> 3) & 1,
            (bits >> 2) & 1,
            (bits >> 1) & 1,
            (bits) & 1)

        return cell_transition

    def set_transitions(self, cell_transition, orientation, new_transitions):
        """
        Set the possible transitions.

        Parameters
        ----------
        cell_transition : int
            64 bits used to encode the valid transitions for a cell.
        orientation : int
            Orientation of the agent inside the cell.
        new_transitions : tuple
            Tuple of new transitions validitiy for the cell.

        Returns
        -------
        int
            An updated bitmap that replaces the original transitions validity
            of `cell_transition' with `new_transitions', for the appropriate
            `orientation'.

        """
spiglerg's avatar
spiglerg committed
395
        mask = (1 << ((8 - orientation) * 8)) - (1 << ((7 - orientation) * 8))
396
397
398
399
400
401
402
403
404
405
406
407
        negmask = ~mask

        new_transitions = \
            (new_transitions[0] & 1) << 7 | \
            (new_transitions[1] & 1) << 6 | \
            (new_transitions[2] & 1) << 5 | \
            (new_transitions[3] & 1) << 4 | \
            (new_transitions[4] & 1) << 3 | \
            (new_transitions[5] & 1) << 2 | \
            (new_transitions[6] & 1) << 1 | \
            (new_transitions[7] & 1)

spiglerg's avatar
spiglerg committed
408
        cell_transition = (cell_transition & negmask) | (new_transitions << ((7 - orientation) * 8))
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433

        return cell_transition

    def get_transition(self, cell_transition, orientation, direction):
        """
        Get the transition bit (1 value) that determines whether an agent
        oriented in direction `orientation' and inside a cell with transitions
        `cell_transition' can move to the cell in direction `direction'
        relative to the current cell.

        Parameters
        ----------
        cell_transition : int
            64 bits used to encode the valid transitions for a cell.
        orientation : int
            Orientation of the agent inside the cell.
        direction : int
            Direction of movement whose validity is to be tested.

        Returns
        -------
        int
            Validity of the requested transition: 0/1 allowed/not allowed.

        """
spiglerg's avatar
spiglerg committed
434
        return ((cell_transition >> ((8 - 1 - orientation) * 8)) >> (8 - 1 - direction)) & 1
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463

    def set_transition(self, cell_transition, orientation, direction,
                       new_transition):
        """
        Set the transition bit (1 value) that determines whether an agent
        oriented in direction `orientation' and inside a cell with transitions
        `cell_transition' can move to the cell in direction `direction'
        relative to the current cell.

        Parameters
        ----------
        cell_transition : int
            64 bits used to encode the valid transitions for a cell.
        orientation : int
            Orientation of the agent inside the cell.
        direction : int
            Direction of movement whose validity is to be tested.
        new_transition : int
            Validity of the requested transition: 0/1 allowed/not allowed.

        Returns
        -------
        int
            An updated bitmap that replaces the original transitions validity
            of `cell_transition' with `new_transitions', for the appropriate
            `orientation'.

        """
        if new_transition:
spiglerg's avatar
spiglerg committed
464
            cell_transition |= (1 << ((8 - 1 - orientation) * 8 + (8 - 1 - direction)))
465
        else:
spiglerg's avatar
spiglerg committed
466
            cell_transition &= ~(1 << ((8 - 1 - orientation) * 8 + (8 - 1 - direction)))
467
468
469
470
471

        return cell_transition

    def rotate_transition(self, cell_transition, rotation=0):
        """
maljx's avatar
maljx committed
472
        Clockwise-rotate a 64-bit transition bitmap by
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
        rotation={0, 45, 90, 135, 180, 225, 270, 315} degrees.

        Parameters
        ----------
        cell_transition : int
            64 bits used to encode the valid transitions for a cell.
        rotation : int
            Angle by which to clock-wise rotate the transition bits in
            `cell_transition' by. I.e., rotation={0, 45, 90, 135, 180,
            225, 270, 315} degrees.

        Returns
        -------
        int
            An updated bitmap that replaces the original transitions bits
            with the equivalent bitmap after rotation.

        """
        # TODO: WARNING: this part of the function has never been tested!

        # Rotate the individual bits in each block
        value = cell_transition
        rotation = rotation // 45
        for i in range(8):
            block_tuple = self.get_transitions(value, i)
            block_tuple = block_tuple[rotation:] + block_tuple[:rotation]
            value = self.set_transitions(value, i, block_tuple)

        # Rotate the 8bits blocks
spiglerg's avatar
spiglerg committed
502
        value = ((value & (2**(rotation * 8) - 1)) << ((8 - rotation) * 8)) | (value >> (rotation * 8))
503
504

        cell_transition = value
505
506
507
508

        return cell_transition


509
class RailEnvTransitions(Grid4Transitions):
510
511
512
    """
    Special case of `GridTransitions' over a 2D-grid, with a pre-defined set
    of transitions mimicking the types of real Swiss rail connections.
513

spmohanty's avatar
spmohanty committed
514
    --------------------------------------------------------------------------
515

spiglerg's avatar
spiglerg committed
516
    As no diagonal transitions are allowed in the RailEnv environment, the
517
    possible transitions for RailEnv from a cell to its neighboring ones
518
    are represented over 16 bits.
519

520
521
522
523
    The 16 bits are organized in 4 blocks of 4 bits each, the direction that
    the agent is facing.
    E.g., the most-significant 4-bits represent the possible movements (NESW)
    if the agent is facing North, etc...
524

525
526
    agent's direction:          North    East   South   West
    agent's allowed movements:  [nesw]   [nesw] [nesw]  [nesw]
527
    example:                     1000     0000   0010    0000
528

529
530
    In the example, the agent can move from North to South and viceversa.
    """
531

532
533
534
535
536
    """
    transitions[] is indexed by case type/id, and returns the 4x4-bit [NESW]
    transitions available as a function of the agent's orientation
    (north, east, south, west)
    """
537
538

    transition_list = [int('0000000000000000', 2),  # empty cell - Case 0
gmollard's avatar
gmollard committed
539
540
541
                       int('1000000000100000', 2),  # Case 1 - straight
                       int('1001001000100000', 2),  # Case 2 - simple switch
                       int('1000010000100001', 2),  # Case 3 - diamond drossing
maljx's avatar
maljx committed
542
543
544
                       int('1001011000100001', 2),  # Case 4 - single slip
                       int('1100110000110011', 2),  # Case 5 - double slip
                       int('0101001000000010', 2),  # Case 6 - symmetrical
545
                       int('0010000000000000', 2),  # Case 7 - dead end
maljx's avatar
maljx committed
546
547
548
                       int('0100000000000010', 2),  # Case 1b (8)  - simple turn right
                       int('0001001000000000', 2),  # Case 1c (9)  - simple turn left
                       int('1100000000100010', 2)]  # Case 2b (10) - simple switch mirrored
549
550
551

    def __init__(self):
        super(RailEnvTransitions, self).__init__(
552
            transitions=self.transition_list
spiglerg's avatar
spiglerg committed
553
        )
554
555
556
557
        
        # These bits represent all the possible dead ends
        self.maskDeadEnds = 0b0010000110000100

maljx's avatar
maljx committed
558
559
560
561
562
563
564
565
566
567
568
        # create this to make validation faster
        self.transitions_all = []
        for index, trans in enumerate(self.transitions):
            self.transitions_all.append(trans)
            if index in (2, 4, 6, 7, 8, 9, 10):
                for _ in range(3):
                    trans = self.rotate_transition(trans, rotation=90)
                    self.transitions_all.append(trans)
            elif index in (1, 5):
                trans = self.rotate_transition(trans, rotation=90)
                self.transitions_all.append(trans)
maljx's avatar
maljx committed
569

570
571
    def print(self, cell_transition):
        print("  NESW")
Mattias Ljungstrom's avatar
Mattias Ljungstrom committed
572
573
574
575
        print("N", format(cell_transition >> (3*4) & 0xF, '04b'))
        print("E", format(cell_transition >> (2*4) & 0xF, '04b'))
        print("S", format(cell_transition >> (1*4) & 0xF, '04b'))
        print("W", format(cell_transition >> (0*4) & 0xF, '04b'))
576

577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
    def repr(self, cell_transition, version=0):
        """
        Provide a string representation of the cell transitions.
        This class doesn't represent an individual cell,
        but a way of interpreting the contents of a cell.
        So using the ad hoc name repr rather than __repr__.
        """
        # binary format string without leading 0b
        sbinTrans = format(cell_transition, "#018b")[2:]
        if version == 0:
            sRepr = " ".join([
                "{}:{}".format(sDir, sbinTrans[i:i+4])
                for i, sDir in
                    zip(
                        range(0, len(sbinTrans), 4),
                        self.lsDirs  # NESW
                    )])
            return sRepr

        if version == 1:
            lsRepr = []
            for iDirIn in range(0, 4):
                sDirTrans = sbinTrans[iDirIn*4:iDirIn*4+4]
                if sDirTrans == "0000":
                    continue
                sDirsOut = [
                    self.lsDirs[iDirOut]
                    for iDirOut in range(0, 4)
                    if sDirTrans[iDirOut] == "1"
                    ]
                lsRepr.append(self.lsDirs[iDirIn] + ":" + "".join(sDirsOut))

            return ", ".join(lsRepr)

maljx's avatar
maljx committed
611
612
613
614
615
616
617
618
619
620
621
622
623
624
    def is_valid(self, cell_transition):
        """
        Checks if a cell transition is a valid cell setup.

        Parameters
        ----------
        cell_transition : int
            64 bits used to encode the valid transitions for a cell.

        Returns
        -------
        Boolean
            True or False
        """
maljx's avatar
maljx committed
625
        for trans in self.transitions_all:
maljx's avatar
maljx committed
626
627
628
629
            if cell_transition == trans:
                return True
        return False

630
    def has_deadend(self, cell_transition):
631
        if cell_transition & self.maskDeadEnds > 0:
632
633
634
635
            return True
        else:
            return False

636
637
638
    def remove_deadends(self, cell_transition):
        cell_transition &= cell_transition & (~self.maskDeadEnds) & 0xffff
        return cell_transition