Information Technology Reference
In-Depth Information
degree 1
under the following condition: when
A
is an answer set of
P
, then
A
satisfies all rules
of
P
. For example, let us plan a vacation: Normally you prefer to go to Mallorca but also
to Stockholm (denoted by the preference relation
≺
). Usually people prefer Mallorca over
Stockholm, unless it is hot. If it is hot Mallorca is preferred over Stockholm. In summer it is
normally hot, but there are exceptions. If it is winter, then Mallorca is no long considered (cf.
Brewka (2002)).
Stockholm
≺
Mallorca
←
not
hot
(rule 1)
Mallorca
≺
Stockholm
←
hot
(rule 2)
hot
←
not
¬
hot
,
summer
(rule 3)
¬
←
rain
(rule 4)
Without further information about the weather we obtain the single preferred answer set
A
1
=
{
Mallorca
, there is no information that it might be
hot
, so rule 1 will determine
preferences.
A
1
satisfies all rules to degree 1. Now if we add a new fact
summer
, then the
new answer set is
Stockholm
}
{
summer
,
hot
,
Mallorca
}
. If we add the literal
hot
, then the new answer set
is
{
summer
,
¬
hot
,
Stockholm
}
. Finally, if we add the facts
summer
and
rain
. The single answer
set is
, we see that it is not possible to satisfy all rules
to degree 1. As in real life there are situations where the best options simply do not work out,
there for LPODs are very well suited for representing problems where a certain choice has to
be made. In general, using ASP we can optimize the solution we want to generate, we can
improve the rules and define the constraints we are using to get the maximum optimization
of the desired answer sets (solutions) (cf. Brewka (2002)). Assurance, as introduced in section
4, pursues similar goals.
{
summer
,
rain
,
hot
,
¬
Mallorca
,
Stockholm
}
2.1.2 Guess and check programs in answer set programming
Answer set programming (ASP) is widely used, expressing properties in NP (i.e. properties
whose verification can be done in polynomial time), where answer sets of normal logic
programs can be generated through solutions and polynomial time proofs for such properties.
The solution of such problems can be carried out in two steps:
1. Generate a candidate solution through a logic program
2. Check the solution by another logic program (cf. Eiter & Polleres (2006))
However, it is often not clear how to combine
Π
guess
and
Π
check
into a single program
Π
solve
∨
Π
solve
does not work,
which solves the overall problem. If we simply take the union
Π
guess
so we have to rewrite the program.
Theoretical results prove that for problems with
2
Σ
complexity, it is required that
Π
check
is
rewritten into a disjunctive logic program
`
Π
check
such that the answer sets of
Π
solve
=
Π
guess
∨
Π
check
yield the solutions of the problem, where
`
`
Π
check
emulates the inconsistency check for
`
Π
check
as a minimal model check, which is co-NP-complete for disjunctive programs. This
becomes even more complicated by the fact that
`
Π
check
must not crucially rely the use of
negation, since it is essentially determined by the
Π
guess
part. These difficulties can make
Π
check
to
`
rewriting
Π
check
a formidable and challenging task (cf. Eiter & Polleres (2006)).
As an example, if we are talking about planning the problem to find a sequence of actions,
which it takes the system from an initial state
p
0
to a state
p
n
, where the states are
changing over the time. Conformant planning looks for a plan
L
which works under all
contingencies cases that may be caused by incomplete information about the initial state
and/or nondeterministic actions effects which is
2
under certain restrictions (see Eiter &
Polleres (2006)). We consider the problem of the"fire alarm", we have an alarm that there is a
Σ
Search WWH ::
Custom Search