archives

Optimization Rules in DLV for the Bridge Crossing Problem


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Ranu, Sayan, Balakrishnan, Prabhakar and Prabhu, G.M. (2006) Optimization Rules in DLV for the Bridge Crossing Problem. Technical Report 06-08, Computer Science, Iowa State University.

Full text available as:Adobe PDF

Abstract

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.

Keywords:Disjunctive logic programming, Datalog programs, bridge crossing problem, optimal strategies, DLV Java wrapper.
Subjects:Computing Methodologies: ARTIFICIAL INTELLIGENCE: Knowledge Representation Formalisms and Methods (F.4.1)
ID code:00000417
Deposited by:G.M. Prabhu on 17 April 2006



Contact site administrator at: ssg@cs.iastate.edu