Ariba Siddiqui
Ariba Siddiqui

Reputation: 45

Implementaion of hmax for directed unfolding of Petri nets

Can somebody please help me try to understand if my implmentation and assumptions are right? Unfortunately, I do not have any means to reproduce it.

I'm trying to implement a heuristic function hmax for directed unfolding of Petri nets from a paper here. TLDR; it estimates a value for the remaining distance from one marking (argument a in my function) to another marking (b) based upon the definition given in the link. You do not need to know what a Mark or a Configuration is, just need to know how Petri nets work.

The paper uses 1 + min() in their definition but since I'm using cost-based directed unfolding, I use a cost_function too. Also, since the computation is cyclic, it might end up in a loop during recursion, hence I use an in_stack to keep track of calls. Whenever a loop is detected the function returns inf and since I use min over all the paths, the distance should be computed over non-looping paths. Another addition from my side is in:

if len(possible_candidates) == 0:
   return 0

Not sure if this is a right assumption. I cannot explain why possible_candidates sometimes is 0.

            def compute_hmax(
                self,
                mark: frozenset[PetriNet.Place],
                target: Set[PetriNet.Place],
                cost_function,
            ):
                if len(mark) == 0:
                    self.local_configuration.hmax = 0
                else:
                    in_stack = (
                        dict()
                    )  # stack to detect visited nodes in the search to detect cycles
                    d = self.hmax(mark, frozenset(target), in_stack, cost_function)
                    self.local_configuration.hmax = d

            @cached(
                cache={},
                key=lambda self, a, b, in_stack, cost_function: hashkey((a, b)),
            )
            def hmax(
                self,
                a: frozenset[PetriNet.Place],
                b: frozenset[PetriNet.Place],
                in_stack,
                cost_function,
            ):
                if b.issubset(a):
                    return 0

                elif len(b) == 1:
                    q = list(b)[0]

                    if q in in_stack:
                        return float("inf")  # cycle detected

                    in_stack[q] = True

                    pre_trans = set(map(lambda arc: arc.source, q.in_arcs))

                    possible_candidates = list(
                        map(
                            lambda t: (
                                t,
                                self.hmax(
                                    a, frozenset(t.preset), in_stack, cost_function
                                ),
                            ),
                            pre_trans,
                        )
                    )

                    in_stack.pop(q)

                    if len(possible_candidates) == 0:
                        return 0

                    min_d_tup = min(possible_candidates, key=lambda t: t[1] + cost_function[t[0]])

                    return cost_function[min_d_tup[0]] + min_d_tup[1]

                else:
                    return max(
                        list(
                            map(
                                lambda t: self.hmax(
                                    a, frozenset({t}), in_stack, cost_function
                                ),
                                b,
                            )
                        )
                    )

Upvotes: 0

Views: 70

Answers (0)

Related Questions