Natasha Alechina

Date: 15:15 – 16:00, Friday, 04.02.2020
Location: Minnaert – 2.02

Title: Synthesis of Process Plans for Manufacturing
Abstract: This talk is based on joint work with Tomas Brazdil, Giuseppe De Giacomo, Paolo Felli, Brian Logan, and Moshe Vardi, published in AAAI 2018 and AAAI 2019. It is an extended version of the talk I gave in April last year for my job interview: apologies to people who already heard a shorter version. The talk is on automated generation of process plans (“controllers”) for sets of manufacturing resources (such as, manufacturing robots). We model manufacturing resources and manufacturing processes (what needs to be done) as transducers (automata with output). The problem of whether a given manufacturing process can be realized by a given set of manufacturing resources can then be stated as an orchestration problem (existence of a controller problem) for transducers. We prove that this problem is decidable in 2EXPTIME if the set of manufacturing resources is known and fixed in advance. This corresponds to making a process plan for a given manufacturing facility. However if the question is, how many machines of each type are needed to implement some manufacturing process, the problem becomes undecidable, in the general case. For uni-transducers (transducers with a single input and a single output port), the problem remains decidable in 2EXPTIME. In addition, the (Pareto) optimal set of resources necessary to manufacture a product is computable for uni-transducers.