transitions.py 19.4 KB
Newer Older
1
2
3
4
5
6
7
8
9
"""
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.
"""


class Transitions:
    """
10
11
    Base Transitions class.

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

17
    def get_transitions(self, cell_transition, orientation):
18
19
20
21
22
23
        """
        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).
24
25
26
27

        Parameters
        ----------
        cell_transition : [cell content]
spiglerg's avatar
spiglerg committed
28
            The object is specific to each derived class (e.g., for
29
30
31
32
33
34
35
36
37
38
            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.

39
40
41
        """
        raise NotImplementedError()

42
    def set_transitions(self, cell_transition, orientation, new_transitions):
43
44
45
46
47
        """
        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.
48
49
50
51

        Parameters
        ----------
        cell_transition : [cell-content]
spiglerg's avatar
spiglerg committed
52
            The object is specific to each derived class (e.g., for
53
54
55
56
57
58
59
60
61
62
63
64
65
66
            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'.

67
68
69
        """
        raise NotImplementedError()

70
    def get_transition(self, cell_transition, orientation, direction):
71
72
73
74
75
        """
        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.
76
77
78
79

        Parameters
        ----------
        cell_transition : [cell-content]
spiglerg's avatar
spiglerg committed
80
            The object is specific to each derived class (e.g., for
81
82
83
84
85
86
87
88
89
90
91
92
93
            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...)

94
95
96
        """
        raise NotImplementedError()

97
98
    def set_transition(self, cell_transition, orientation, direction,
                       new_transition):
99
100
101
102
103
104
        """
        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'.
105
106
107
108

        Parameters
        ----------
        cell_transition : [cell-content]
spiglerg's avatar
spiglerg committed
109
            The object is specific to each derived class (e.g., for
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
            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'.

127
128
129
130
        """
        raise NotImplementedError()


131
class Grid4Transitions(Transitions):
132
    """
133
    Grid4Transitions class derived from Transitions.
134

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

    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]
155
    example:                     1000     0000   0010    0000
156
157

    In the example, the agent can move from North to South and viceversa.
158
159
    """

160
    def __init__(self, transitions):
161
162
        self.transitions = transitions

163
    def get_transitions(self, cell_transition, orientation):
164
165
166
167
168
        """
        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'.
169
170
171
172

        Parameters
        ----------
        cell_transition : int
173
            16 bits used to encode the valid transitions for a cell.
174
175
176
177
178
179
180
181
        orientation : int
            Orientation of the agent inside the cell.

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

182
        """
183
184
        bits = (cell_transition >> ((3-orientation)*4))
        return ((bits >> 3) & 1, (bits >> 2) & 1, (bits >> 1) & 1, (bits) & 1)
185

186
    def set_transitions(self, cell_transition, orientation, new_transitions):
187
188
189
190
191
192
        """
        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'.
193
194
195
196

        Parameters
        ----------
        cell_transition : int
197
            16 bits used to encode the valid transitions for a cell.
198
199
200
201
202
203
204
205
206
207
208
209
        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'.

210
        """
211
212
213
214
215
216
217
218
219
220
221
222
        mask = (1 << ((4-orientation)*4)) - (1 << ((3-orientation)*4))
        negmask = ~mask

        new_transitions = \
            (new_transitions[0] & 1) << 3 | \
            (new_transitions[1] & 1) << 2 | \
            (new_transitions[2] & 1) << 1 | \
            (new_transitions[3] & 1)

        cell_transition = \
            (cell_transition & negmask) | \
            (new_transitions << ((3-orientation)*4))
223
224
225

        return cell_transition

226
    def get_transition(self, cell_transition, orientation, direction):
227
228
229
230
231
        """
        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.
232
233
234
235

        Parameters
        ----------
        cell_transition : int
236
            16 bits used to encode the valid transitions for a cell.
237
238
239
240
241
242
243
244
245
246
        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.

247
        """
maljx's avatar
maljx committed
248
249
        return ((cell_transition >> ((4-1-orientation) * 4)) >>
                (4-1-direction)) & 1
250
251
252

    def set_transition(self, cell_transition, orientation, direction,
                       new_transition):
253
254
255
256
257
        """
        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.
258
259
260
261

        Parameters
        ----------
        cell_transition : int
262
            16 bits used to encode the valid transitions for a cell.
263
264
265
266
267
268
269
270
271
272
273
274
275
276
        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'.

277
278
        """
        if new_transition:
maljx's avatar
maljx committed
279
280
            cell_transition |= (1 << ((4-1-orientation) * 4 +
                                (4-1-direction)))
281
282
        else:
            cell_transition &= \
283
                ~(1 << ((4-1-orientation) * 4 +
maljx's avatar
maljx committed
284
                        (4-1-direction)))
285
286
287
288
289

        return cell_transition

    def rotate_transition(self, cell_transition, rotation=0):
        """
290
291
        Clockwise-rotate a 16-bit transition bitmap by
        rotation={0, 90, 180, 270} degrees.
spiglerg's avatar
spiglerg committed
292
293
294
295

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

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

307
        """
308
309
310
311
312
313
314
315
316
317
318
        # 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)
            block_tuple = block_tuple[(
                4-rotation):] + block_tuple[:(4-rotation)]
            value = self.set_transitions(value, i, block_tuple)

        # Rotate the 4-bits blocks
        value = ((value & (2**(rotation*4)-1)) <<
maljx's avatar
maljx committed
319
                 ((4-rotation)*4)) | (value >> (rotation*4))
320
321
322
323
324
325
326
327

        cell_transition = value
        return cell_transition


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

329
330
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
361
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
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
    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.

        """
        bits = (cell_transition >> ((7-orientation)*8))
        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'.

        """
        mask = (1 << ((8-orientation)*8)) - (1 << ((7-orientation)*8))
        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)

        cell_transition = (cell_transition & negmask) | (
            new_transitions << ((7-orientation)*8))

        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.

        """
        return ((cell_transition >> ((8-1-orientation) * 8)) >>
maljx's avatar
maljx committed
433
                (8-1-direction)) & 1
434
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
464

    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:
            cell_transition |= (1 << ((8-1-orientation) * 8 +
                                (8 - 1 - direction)))
465
        else:
466
467
468
469
470
471
472
            cell_transition &= ~(1 << ((8-1-orientation) * 8 +
                                 (8 - 1 - direction)))

        return cell_transition

    def rotate_transition(self, cell_transition, rotation=0):
        """
maljx's avatar
maljx committed
473
        Clockwise-rotate a 64-bit transition bitmap by
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
502
503
        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
        value = ((value & (2**(rotation*8)-1)) <<
maljx's avatar
maljx committed
504
                 ((8-rotation)*8)) | (value >> (rotation*8))
505
506

        cell_transition = value
507
508
509
510

        return cell_transition


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

spmohanty's avatar
spmohanty committed
516
    --------------------------------------------------------------------------
517

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

522
523
524
525
    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...
526

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

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

534
535
536
537
538
    """
    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)
    """
539
540

    transition_list = [int('0000000000000000', 2),  # empty cell - Case 0
gmollard's avatar
gmollard committed
541
542
543
                       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
544
545
546
                       int('1001011000100001', 2),  # Case 4 - single slip
                       int('1100110000110011', 2),  # Case 5 - double slip
                       int('0101001000000010', 2),  # Case 6 - symmetrical
gmollard's avatar
gmollard committed
547
                       int('0010000000000000', 2)]  # Case 7 - dead end
548
549
550

    def __init__(self):
        super(RailEnvTransitions, self).__init__(
551
            transitions=self.transition_list
spiglerg's avatar
spiglerg committed
552
        )