Symbolic Heuristic Search
Bo Huang, MengChu Zhou · 2020
To fast schedule resource allocation systems (RASs), this chapter presents a symbolic A* search approach to compactly represent and efficiently manipulate SC-nets of RASs. First, RASs are modeled by SC-nets where time information is associated with activity places. The chapter briefly reviews the basic concepts of Boolean algebra and binary decision diagrams (BDDs). Then, the procedures to functionally represent, evolve, and schedule these timed SC-nets are given by combining BDDs and the A* search. A resource allocation system can be modeled by a place-timed SC-net via a conversion method from an existing untimed Petri net or a top-down or bottom-up modeling method. The chapter shows how to symbolically represent and evolve a place-timed SC-net via BDDs. It also proposes an admissible heuristic function suitable for the symbolic method and for its efficient functional implementation.