Technical Report Number
Disjunctive logic programming is a powerful tool in knowledge representation and commonsense reasoning. The first solid implementation of a DLP system is called DLV (Datalog with Vel). In this paper we offer three strategies to produce optimal solutions in DLV for the well-known Bridge Crossing Problem. These strategies are a piggyback strategy, a non-piggyback strategy, and a mixed strategy. An analysis to determine the number of time steps required for an optimal solution using these strategies is provided. We also characterize and prove the conditions under which a particular strategy should be used to obtain an optimal solution. These strategies are implemented in the form of optimization rules in a DLV program for the bridge crossing problem. Preliminary results indicate a drastic reduction in execution time when compared to other DLV programs for bridge crossing which do not incorporate these strategies. Our implementation uses a DLV Java wrapper, allowing us to embed disjunctive logic programs inside an object-oriented environment.