Page - 35 - in Joint Austrian Computer Vision and Robotics Workshop 2020

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