Reputation: 45
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