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

TowardsASP-basedScheduling forIndustrialTransportVehicles Felicitas Fabricius MarcoDeBortoli GeraldSteinbauer GrazUniversityofTechnology {mbortoli,steinbauer}@ist.tugraz.at MaximilianSelmair BMWGroup maximilian.selmair@bmw.de MichaelReip Incubed IT m.reip@incubedit.com MartinGebser Universita¨t Klagenfurt martin.gebser@aau.at Abstract. The increasing number of robots and autonomous vehicles involved in logistics applications leads to new challenges to face for the community of Arti- ficial Intelligence. Web-shop giants, like Amazon or Alibaba for instance, brought this problem to a new level, with huge warehouses and a huge num- ber of orders to deliver with strict deadlines. Coor- dinating and scheduling such high quantity of tasks over a fleet of autonomous robots is a really com- plex problem: neither simple imperative greedy al- gorithms, which compromises over the quality of the solution, nor precise enumeration techniques, which make compromises over the solving time, are any- more feasible to tackle such problems. In this work, weuseAnswerSetProgrammingtotacklereal-world logistics problems, involving both dynamic task as- signment and planning, at the BMWGroup and In- cubedIT. Different strategies are tried, and com- pared to the original imperativeapproach. 1. Introduction Industry 4.0 is bringing more and more interest toward the digitalization of all productive stages in the industrial field. Even before that, we all have been witnesses of the big impact robotics had in industry, by the automatization of repetitive tasks. In the last years, thanks to the increasing computa- tionalpower,Artificial Intelligence (AI) is spreading as well, leading to the next step of the integration between robots and production: the automatization of complex tasks requiring reasoning. In this per- spective, optimization of logistics is crucial for large companies, in order to save both time and money. Still we are dealing with a production environment which considers a fleet of robots floating around, ef- ficiently performing tasks and carrying goods where to model such NP-hard domains a high number of constraints is needed. For this reason, a imperative approach become more and more difficult to main- tain, and cannot benefit from the numerous meta- heuristics and optimizations (if not manually imple- mented) already encoded inside the solvers of other programming paradigms, like declarative program- ming. Answer Set Programming (ASP) is a fast and intuitive logic language,whichalreadyhasmanyap- plications both in industry and in research (see Sec- tion 2). In this paper we are going to investigate the difference between the two paradigms, by replacing theimperativepartof thetaskschedulersusedbytwo companies, theBMWGroupandIncubedIT,withan ASP implementation. While classical languages are well suited for greedy algorithms implementation, declarative programming has other advantages: first of all, the focus is on the description of the problem, leaving all the solving details to the external solver. Moreover, most solvers are configurable with a lot of meta-heuristics to cut the search space: the user hasonly tofindtheonewhichfits theproblembetter, without implementing anything. Then, since logic languages are basically based on enumeration tech- niques, an ASP solver looks for the best solution, or at least the best one in a given time. Depending on the size of the instance, this behaviour leads to hugecomputational timewith respect toagreedyal- 34