Seite - 35 - in Joint Austrian Computer Vision and Robotics Workshop 2020
Bild der Seite - 35 -
Text der Seite - 35 -
gorithm. We are interested into the analysis of this
trade-off between greedy solving time and declara-
tive solution quality. This paper isbased on Felicitas
FabriciusâMaster thesis [6].
2.RelatedResearchandASPFoundations
The demand for increased complexity and scala-
bility in industry automatization requires more and
more powerful techniques and algorithms. Impera-
tiveprogrammingissuitable towriteaveryproblem-
specific solution. However, the development of such
kind of code can be really arduous, time expensive
and difficult to maintain. Optimal task scheduling
and planning, enriched by domain-based heuristics,
requires a huge amount of code lines if written with
an imperative language [17].
Answer Set Programming, and logic program-
mingingeneral, allowsto tacklecombinatorialprob-
lem in a very intuitive way, splitting the work into
twophases: thedescriptionof theproblemanditsef-
ficient solving procedure [7]. The programmer has
only to care of the former, and this requires just
a fragment of the effort required by an imperative
language. Then, (s)he can use one of the solvers
available in the market, like Clingo or DLV, to find
the optimal solution, improving it with a large set
of meta-heuristics. Although the most common ap-
proach is the imperativeone,manyuse-casesofASP
applied to industry can be found in the literature: in
2017, Dodaro and Maratea designed a shift plan for
164Italiannurses,calculatingtheoptimalplanforan
entire year in just 50 minutes, using the state-of-the-
art solver Clingo [3]. Staying in the shift scheduling
field, the DLV solver was deployed to find the opti-
mal shift plan for seaport workers [14]. In this case,
theproblemwascomplicatedby thefact that theem-
ployees have different qualifications, and there were
different kinds of tasks. Finding of the optimal one
month-longplanrequired8minutes. Asimilarwork,
considering different demands as well, is described
in [2]. Moving to other kind of industrial fields,
ASPwasused inE-tourisminorder tofind the travel
which suits the user the most [1]. In [12] the au-
thorsusedASPforphoneroutingincallcenters. The
customer was classified in a category and assigned
directly to the human operator. We can find plenty
of ASP applications regarding task assignment and
routing as well. Examples can be found in [4], [16],
[10], [13]and [15].
Answer Set Programming is based on the stable modelsemantics,presentedbyGelfondandLifschitz
in [11] for dealing with logic programs with nega-
tion as failure. With the following we give a quick
overviewof the languagesemantics [2,7].
A ruler ina logicprogramisanexpressionof the
form
hâa1, .. . ,am,ÂŹam+1, .. . ,ÂŹan (1)
wherea1, .. . ,anareatomsoftheforms(t1, .. . ,tk),
in which s is a predicate symbol and t1, .. . ,tk are
terms, viz. constants, variables, or functions, andÂŹ
stands for default negation. The head h of r is ei-
ther an atom a, a choice {a}, or the special sym-
bolâ„. Ifh is an atom andn= 0, we call r a fact,
a choice rule ifh is{a}, and an integrity constraint
ifh isâ„; we skipâ orâ„, respectively, when writ-
ing rules (1) with n = 0 and integrity constraints.
A logic programP is a set of rules and constraints.
In the first-order case, terms occurring in P may
include arithmetic expressions, and atoms may be
based on relational operators like â<â. On the other
hand, a term, atom, rule, constraint, or program is
ground if itdoesnot includevariables,arithmeticex-
pressions, or relational operators. A first-order pro-
gram P stands for the set grd(P) of all instances
of rules and constraints constructible by substituting
ground terms for variables and evaluating arithmetic
expressionsaswellasrelationaloperatorsinthestan-
dard way. For details on ground instantiation, we
refer the interested reader to [5, 9]. The semantics
of a logic programP is given by its stable models,
which are particular sets of (true) ground atoms as
defined in the following. The reductPX relative to
a setX of ground atoms is the set of all rules and
constraints in grd(P) such that{a1, .. . ,am}âX,
{am+1, .. . ,an}â©X=â
, andaâX ifh={a} isa
choice for a rule (1). Then,X is a stable model ofP
if it isâ-minimal among the sets of ground atoms
such that, for all rules inPX, {a1, .. . ,am} â X
implieshâX oraâX ifh= {a}. In addition to
rules,a logicprogramcancontain#minimizestate-
mentsof the form
#minimize[`1 =w1@L1, .. . ,`n=wn@Ln].
Besides literals `i and integer weightswi for 1 â€
iâ€n, a #minimize statement includes integersLi
providing priority levels [8]. The #minimize state-
ments inP distinguish optimal answer sets ofP in
the following way. For any setX of atoms and inte-
gerL, letÎŁXL denote thesumofweightswi such that
35
Joint Austrian Computer Vision and Robotics Workshop 2020
- Titel
- Joint Austrian Computer Vision and Robotics Workshop 2020
- Herausgeber
- Graz University of Technology
- Ort
- Graz
- Datum
- 2020
- Sprache
- englisch
- Lizenz
- CC BY 4.0
- ISBN
- 978-3-85125-752-6
- Abmessungen
- 21.0 x 29.7 cm
- Seiten
- 188
- Kategorien
- Informatik
- Technik