Menu
▾
▴
[dlvhex-notify] SF.net SVN: dlvhex:[3561] dlvhex/branches/dlvhex-refactoring
|
From: <chr...@us...> - 2012-02-23 13:38:03
|
Revision: 3561
http://dlvhex.svn.sourceforge.net/dlvhex/?rev=3561&view=rev
Author: chrisr86
Date: 2012-02-23 13:37:53 +0000 (Thu, 23 Feb 2012)
Log Message:
-----------
add simple rule for global learning
Modified Paths:
--------------
dlvhex/branches/dlvhex-refactoring/include/dlvhex2/BaseModelGenerator.h
dlvhex/branches/dlvhex-refactoring/include/dlvhex2/ClaspSolver.h
dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuinePlainModelGenerator.h
dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuineSolver.h
dlvhex/branches/dlvhex-refactoring/include/dlvhex2/InternalGroundASPSolver.h
dlvhex/branches/dlvhex-refactoring/include/dlvhex2/Nogood.h
dlvhex/branches/dlvhex-refactoring/src/BaseModelGenerator.cpp
dlvhex/branches/dlvhex-refactoring/src/ClaspSolver.cpp
dlvhex/branches/dlvhex-refactoring/src/GenuinePlainModelGenerator.cpp
dlvhex/branches/dlvhex-refactoring/src/GenuineSolver.cpp
dlvhex/branches/dlvhex-refactoring/src/InternalGroundASPSolver.cpp
dlvhex/branches/dlvhex-refactoring/src/InternalGroundDASPSolver.cpp
dlvhex/branches/dlvhex-refactoring/src/dlvhex.cpp
dlvhex/branches/dlvhex-refactoring/testsuite/TestPlugin.cpp
Modified: dlvhex/branches/dlvhex-refactoring/include/dlvhex2/BaseModelGenerator.h
===================================================================
--- dlvhex/branches/dlvhex-refactoring/include/dlvhex2/BaseModelGenerator.h 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/include/dlvhex2/BaseModelGenerator.h 2012-02-23 13:37:53 UTC (rev 3561)
@@ -37,6 +37,10 @@
#include "dlvhex2/Interpretation.h"
#include "dlvhex2/ASPSolverManager.h"
#include "dlvhex2/Atoms.h"
+#include "dlvhex2/ID.h"
+#include "dlvhex2/Registry.h"
+#include "dlvhex2/Nogood.h"
+#include "dlvhex2/GenuineSolver.h"
#include <list>
#include "dlvhex2/CDNLSolver.h"
@@ -90,6 +94,22 @@
OrdinaryAtom replacement;
};
+ // ========== Global Learning ==========
+
+ // computes the set of predicate IDs which are relevant
+ // to a certain edb+idb
+ std::set<ID> getPredicates(const RegistryPtr reg, InterpretationConstPtr edb, const std::vector<ID>& idb);
+
+ // restricts an interpretation to the atoms over specified predicates
+ InterpretationPtr restrictInterpretationToPredicates(const RegistryPtr reg, InterpretationConstPtr intr, const std::set<ID>& predicates);
+
+ // converts an interpretation into a nogood
+ Nogood interpretationToNogood(InterpretationConstPtr intr, NogoodContainer& ngContainer);
+
+ void globalConflictAnalysis(ProgramCtx& ctx, const std::vector<ID>& idb, GenuineSolverPtr solver);
+
+ // ========== ==========
+
// projects input interpretation for predicate inputs
// calculates constant input tuples from auxiliary input predicates and from given constants
// calls eatom function with each input tuple
Modified: dlvhex/branches/dlvhex-refactoring/include/dlvhex2/ClaspSolver.h
===================================================================
--- dlvhex/branches/dlvhex-refactoring/include/dlvhex2/ClaspSolver.h 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/include/dlvhex2/ClaspSolver.h 2012-02-23 13:37:53 UTC (rev 3561)
@@ -142,6 +142,8 @@
std::map<IDAddress, Clasp::Literal> hexToClasp; // reverse index is not possible as multiple HEX IDs may be mapped to the same clasp ID
std::map<Clasp::Literal, std::vector<IDAddress> > claspToHex;
+ // statistics
+ int modelCount;
public:
ClaspSolver(ProgramCtx& ctx, OrdinaryASPProgram& p);
virtual ~ClaspSolver();
@@ -156,6 +158,7 @@
int getNogoodCount();
virtual InterpretationConstPtr getNextModel();
+ virtual int getModelCount();
InterpretationPtr projectToOrdinaryAtoms(InterpretationConstPtr intr);
typedef boost::shared_ptr<ClaspSolver> Ptr;
Modified: dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuinePlainModelGenerator.h
===================================================================
--- dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuinePlainModelGenerator.h 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuinePlainModelGenerator.h 2012-02-23 13:37:53 UTC (rev 3561)
@@ -72,6 +72,7 @@
// genuine solver
GenuineSolverPtr solver;
+ int firstModel;
// InternalGroundASPSolverPtr igas;
// InternalGrounderPtr grounder;
// Interpretation* currentanswer;
Modified: dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuineSolver.h
===================================================================
--- dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuineSolver.h 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/include/dlvhex2/GenuineSolver.h 2012-02-23 13:37:53 UTC (rev 3561)
@@ -73,6 +73,7 @@
public:
virtual std::string getStatistics() = 0;
virtual InterpretationConstPtr getNextModel() = 0;
+ virtual int getModelCount() = 0;
virtual InterpretationPtr projectToOrdinaryAtoms(InterpretationConstPtr inter) = 0;
// virtual int addNogood(Nogood ng) = 0;
// virtual void removeNogood(int index) = 0;
@@ -102,6 +103,7 @@
std::string getStatistics();
InterpretationConstPtr getNextModel();
+ int getModelCount();
InterpretationPtr projectToOrdinaryAtoms(InterpretationConstPtr inter);
int addNogood(Nogood ng);
void removeNogood(int index);
Modified: dlvhex/branches/dlvhex-refactoring/include/dlvhex2/InternalGroundASPSolver.h
===================================================================
--- dlvhex/branches/dlvhex-refactoring/include/dlvhex2/InternalGroundASPSolver.h 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/include/dlvhex2/InternalGroundASPSolver.h 2012-02-23 13:37:53 UTC (rev 3561)
@@ -56,7 +56,10 @@
private:
std::string bodyAtomPrefix;
int bodyAtomNumber;
+
+protected:
bool firstmodel;
+ int modelCount;
protected:
// structural program information
@@ -168,6 +171,7 @@
void removeExternalLearner(LearningCallback* lb);
virtual InterpretationConstPtr getNextModel();
+ virtual int getModelCount();
InterpretationPtr projectToOrdinaryAtoms(InterpretationConstPtr intr);
typedef boost::shared_ptr<InternalGroundASPSolver> Ptr;
Modified: dlvhex/branches/dlvhex-refactoring/include/dlvhex2/Nogood.h
===================================================================
--- dlvhex/branches/dlvhex-refactoring/include/dlvhex2/Nogood.h 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/include/dlvhex2/Nogood.h 2012-02-23 13:37:53 UTC (rev 3561)
@@ -72,10 +72,10 @@
virtual void removeNogood(int index) = 0;
virtual int getNogoodCount() = 0;
- inline ID createLiteral(ID lit){
+ static inline ID createLiteral(ID lit){
return ID(ID::MAINKIND_LITERAL | ID::SUBKIND_ATOM_ORDINARYG | (lit.isNaf() ? ID::NAF_MASK : 0), lit.address);
}
- inline ID createLiteral(IDAddress litadr, bool truthValue = true){
+ static inline ID createLiteral(IDAddress litadr, bool truthValue = true){
return ID(ID::MAINKIND_LITERAL | ID::SUBKIND_ATOM_ORDINARYG | (truthValue ? 0 : ID::NAF_MASK), litadr);
}
Modified: dlvhex/branches/dlvhex-refactoring/src/BaseModelGenerator.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/src/BaseModelGenerator.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/src/BaseModelGenerator.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -114,6 +114,114 @@
return true;
}
+std::set<ID> BaseModelGenerator::getPredicates(const RegistryPtr reg, InterpretationConstPtr edb, const std::vector<ID>& idb){
+
+ std::set<ID> preds;
+
+ // collects edb predicates
+ bm::bvector<>::enumerator en = edb->getStorage().first();
+ bm::bvector<>::enumerator en_end = edb->getStorage().end();
+ while (en < en_end){
+ // check if the predicate is relevant
+ const OrdinaryAtom& ogatom = reg->ogatoms.getByID(ID(ID::MAINKIND_ATOM | ID::SUBKIND_ATOM_ORDINARYG, *en));
+ preds.insert(ogatom.tuple.front());
+ en++;
+ }
+
+ // collects idb predicates
+ BOOST_FOREACH (ID ruleID, idb){
+ assert(ruleID.isRule());
+ const Rule& rule = reg->rules.getByID(ruleID);
+
+ // head
+ BOOST_FOREACH (ID atomID, rule.head){
+ const OrdinaryAtom& atom = atomID.isOrdinaryGroundAtom() ? reg->ogatoms.getByID(atomID) : reg->onatoms.getByID(atomID);
+ preds.insert(atom.tuple.front());
+ }
+
+ // body
+ BOOST_FOREACH (ID atomID, rule.body){
+ if (atomID.isOrdinaryAtom()){
+ const OrdinaryAtom& atom = atomID.isOrdinaryGroundAtom() ? reg->ogatoms.getByID(atomID) : reg->onatoms.getByID(atomID);
+ preds.insert(atom.tuple.front());
+ }
+ if (atomID.isExternalAtom()){
+ const ExternalAtom& atom = reg->eatoms.getByID(atomID);
+ // go through predicate input parameters
+ int i = 0;
+ BOOST_FOREACH (ID param, atom.tuple){
+ if (atom.pluginAtom->getInputType(i++) == PluginAtom::PREDICATE){
+ preds.insert(param);
+ }
+ }
+ }
+ }
+ }
+
+#ifndef NDEBUG
+ std::stringstream ss;
+ ss << "Relevant predicates: ";
+ bool first = true;
+ BOOST_FOREACH (ID p, preds){
+ if (!first) ss << ", ";
+ first = false;
+ ss << p;
+ }
+ DBGLOG(DBG, ss.str());
+#endif
+
+ return preds;
+}
+
+InterpretationPtr BaseModelGenerator::restrictInterpretationToPredicates(const RegistryPtr reg, InterpretationConstPtr intr, const std::set<ID>& predicates){
+
+ InterpretationPtr ointr = InterpretationPtr(new Interpretation(reg));
+
+ // go through ground atoms in interpretation
+ bm::bvector<>::enumerator en = intr->getStorage().first();
+ bm::bvector<>::enumerator en_end = intr->getStorage().end();
+ while (en < en_end){
+ // check if the predicate is relevant
+ const OrdinaryAtom& atom = reg->ogatoms.getByID(ID(ID::MAINKIND_ATOM | ID::SUBKIND_ATOM_ORDINARYG, *en));
+ if (std::find(predicates.begin(), predicates.end(), atom.tuple.front()) != predicates.end()){
+ // yes, set the atom
+ ointr->setFact(*en);
+ }
+ en++;
+ }
+ return ointr;
+}
+
+Nogood BaseModelGenerator::interpretationToNogood(InterpretationConstPtr intr, NogoodContainer& ngContainer){
+
+ Nogood ng;
+
+ // go through ground atoms in interpretation
+ bm::bvector<>::enumerator en = intr->getStorage().first();
+ bm::bvector<>::enumerator en_end = intr->getStorage().end();
+ while (en < en_end){
+ // add the atom to the nogood
+ ng.insert(ngContainer.createLiteral(*en));
+ en++;
+ }
+
+ return ng;
+}
+
+void BaseModelGenerator::globalConflictAnalysis(ProgramCtx& ctx, const std::vector<ID>& idb, GenuineSolverPtr solver){
+
+ DBGLOG(DBG, "Global conflict analysis");
+ if (solver->getModelCount() == 0 && ctx.config.getOption("GlobalLearning")){
+ DBGLOG(DBG, "Contradiction on first model: Component is inconsistent wrt. input");
+ Nogood gng;
+ if (input != InterpretationConstPtr()){
+ gng = interpretationToNogood(restrictInterpretationToPredicates(ctx.registry(), input, getPredicates(ctx.registry(), ctx.edb, idb)), ctx.globalNogoods);
+ }
+ DBGLOG(DBG, "Generating global nogood " << gng);
+ ctx.globalNogoods.addNogood(gng);
+ }
+}
+
// projects input interpretation
// calls eatom function
// reintegrates output tuples as auxiliary atoms into outputi
Modified: dlvhex/branches/dlvhex-refactoring/src/ClaspSolver.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/src/ClaspSolver.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/src/ClaspSolver.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -573,6 +573,7 @@
DBGLOG(DBG, "Initially inconsistent: " << initiallyInconsistent);
// if the program is initially inconsistent we do not need to do a search at all
+ modelCount = 0;
if (initiallyInconsistent){
endOfModels = true;
claspThread = NULL;
@@ -683,8 +684,13 @@
DBGLOG(DBG, "MainThread: Got a model: " << *nextModel);
return nextModel;
}
+ modelCount++;
}
+int ClaspSolver::getModelCount(){
+ return modelCount;
+}
+
InterpretationPtr ClaspSolver::projectToOrdinaryAtoms(InterpretationConstPtr intr){
if (intr == InterpretationConstPtr()){
return InterpretationPtr();
Modified: dlvhex/branches/dlvhex-refactoring/src/GenuinePlainModelGenerator.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/src/GenuinePlainModelGenerator.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/src/GenuinePlainModelGenerator.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -163,6 +163,7 @@
solver = GenuineSolver::getInstance(factory.ctx, program);
factory.ctx.globalNogoods.addNogoodListener(solver);
+ firstModel = true;
//Nogood ng1;
//ng1.insert(solver->createLiteral(29));
@@ -196,6 +197,12 @@
// remove edb from result
InterpretationPtr modelCandidate = solver->projectToOrdinaryAtoms(solver->getNextModel());
+
+ // learn global nogoods
+ if (modelCandidate == InterpretationPtr()){
+ globalConflictAnalysis(factory.ctx, factory.idb, solver);
+ }
+
DBGLOG(DBG, "Statistics:" << std::endl << solver->getStatistics());
return modelCandidate;
}
Modified: dlvhex/branches/dlvhex-refactoring/src/GenuineSolver.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/src/GenuineSolver.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/src/GenuineSolver.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -132,6 +132,10 @@
return solver->getNextModel();
}
+int GenuineSolver::getModelCount(){
+ return solver->getModelCount();
+}
+
InterpretationPtr GenuineSolver::projectToOrdinaryAtoms(InterpretationConstPtr inter){
return solver->projectToOrdinaryAtoms(inter);
}
Modified: dlvhex/branches/dlvhex-refactoring/src/InternalGroundASPSolver.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/src/InternalGroundASPSolver.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/src/InternalGroundASPSolver.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -835,7 +835,7 @@
#endif
}
-InternalGroundASPSolver::InternalGroundASPSolver(ProgramCtx& c, OrdinaryASPProgram& p) : CDNLSolver(c, NogoodSet()), program(p), bodyAtomPrefix(std::string("body_")), bodyAtomNumber(0), firstmodel(true), cntDetectedUnfoundedSets(0){
+InternalGroundASPSolver::InternalGroundASPSolver(ProgramCtx& c, OrdinaryASPProgram& p) : CDNLSolver(c, NogoodSet()), program(p), bodyAtomPrefix(std::string("body_")), bodyAtomNumber(0), firstmodel(true), cntDetectedUnfoundedSets(0), modelCount(0){
DBGLOG(DBG, "Internal Ground ASP Solver Init");
reg = ctx.registry();
@@ -943,9 +943,14 @@
InterpretationConstPtr icp(interpretation);
+ modelCount++;
return icp;
}
+int InternalGroundASPSolver::getModelCount(){
+ return modelCount;
+}
+
InterpretationPtr InternalGroundASPSolver::projectToOrdinaryAtoms(InterpretationConstPtr intr){
if (intr == InterpretationConstPtr()){
Modified: dlvhex/branches/dlvhex-refactoring/src/InternalGroundDASPSolver.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/src/InternalGroundDASPSolver.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/src/InternalGroundDASPSolver.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -238,6 +238,8 @@
#ifndef NDEBUG
++cntDUnfoundedSets;
#endif
+ modelCount--; // model was a spurious one
+
Nogood loopNogood = getViolatedLoopNogood(ufs);
DBGLOG(DBG, "Adding loop nogood: " << loopNogood);
addNogood(loopNogood);
Modified: dlvhex/branches/dlvhex-refactoring/src/dlvhex.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/src/dlvhex.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/src/dlvhex.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -151,6 +151,7 @@
<< " user: Apply user-defined rules for nogood learning" << std::endl
<< " partial: Apply learning rules also when model is still partial" << std::endl
<< " By default, all options are enabled" << std::endl
+ << " --globlearn Enable global learning, i.e., nogood propagation over multiple evaluation units" << std::endl
<< " --noflpcheck Disable FLP check in Guess-and-check model generator" << std::endl
<< " -s, --silent Do not display anything than the actual result." << std::endl
<< " --mlp Use dlvhex+mlp solver (modular nonmonotonic logic programs)" << std::endl
@@ -308,6 +309,7 @@
// default model builder = "online" model builder
pctx.modelBuilderFactory = boost::factory<OnlineModelBuilder<FinalEvalGraph>*>();
+ pctx.config.setOption("GlobalLearning", 0);
pctx.config.setOption("FLPCheck", 1);
pctx.config.setOption("GenuineSolver", 0);
pctx.config.setOption("Instantiate", 0);
@@ -576,6 +578,7 @@
{ "extlearn", optional_argument, 0, 18 },
// { "instantiate", no_argument, 0, 19 },
{ "noflpcheck", no_argument, 0, 20 },
+ { "globlearn", optional_argument, 0, 21 },
{ NULL, 0, NULL, 0 }
};
@@ -956,6 +959,10 @@
pctx.config.setOption("FLPCheck", 0);
break;
+ case 21:
+ pctx.config.setOption("GlobalLearning", 1);
+ break;
+
case '?':
config.pluginOptions.push_back(argv[optind - 1]);
break;
Modified: dlvhex/branches/dlvhex-refactoring/testsuite/TestPlugin.cpp
===================================================================
--- dlvhex/branches/dlvhex-refactoring/testsuite/TestPlugin.cpp 2012-02-22 10:52:27 UTC (rev 3560)
+++ dlvhex/branches/dlvhex-refactoring/testsuite/TestPlugin.cpp 2012-02-23 13:37:53 UTC (rev 3561)
@@ -424,8 +424,8 @@
for (int i = 0; i < t.size(); ++i) at2.tuple.push_back(t[i]);
Nogood nogood;
- nogood.insert(nogoods->createLiteral(getRegistry()->storeOrdinaryGAtom(at1).address, true));
- nogood.insert(nogoods->createLiteral(getRegistry()->storeOrdinaryGAtom(at2).address, false));
+ nogood.insert(NogoodContainer::createLiteral(getRegistry()->storeOrdinaryGAtom(at1).address, true));
+ nogood.insert(NogoodContainer::createLiteral(getRegistry()->storeOrdinaryGAtom(at2).address, false));
nogood.insert(getOutputAtom(ctx, nogoods, query, t, false));
nogoods->addNogood(nogood);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
