Wyniki wyszukiwania - BazTech

1

Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference

Jastrzab Tomasz, Czech Zbigniew J., Wieczorek Wojciech

Fundamenta Informaticae

|

2021

|

Vol. 178, nr 3

203--227

EN

The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard.

2

A Multi-level Refinement Approach for Structural Synthesis of Optimal Probabilistic Models

Benouhiba Toufik

Fundamenta Informaticae

|

2021

|

Vol. 179, nr 1

1--33

EN

Probabilistic models play an important role in many fields such as distributed systems and simulations. Like non-probabilistic systems, they can be synthesized using classical refinement-based techniques, but they also require identifying the probability distributions to be used and their parameters. Since a fully automated and blind refinement is generally undecidable, many works tried to synthesize them by looking for the parameters of the distributions. Syntax-guided synthesizing approaches are more powerful, they try to synthesize models structurally by using context-free grammars. However, many problems arise like huge search space, the complexity of generated models, and the limitation of context-free grammars to define constraints over the structure. In this paper, we propose a multi-step refinement approach, based on meta-models, offering several abstraction levels to reduce the size of the search space. More specifically, each refinement step is divided into two stages in which the desired shape of models is first described by context-sensitive constraints. In the second stage, model templates are instantiated by using global optimization techniques. We use our approach to a synthesize a set of optimal probabilistic models and show that context-sensitive constraints coupled with the multi-level abilities of the approach make the synthesis task more effective.

3

Partial (Neighbourhood) Singleton Arc Consistency for Constraint Satisfaction Problems

Wallace Richard J.

Fundamenta Informaticae

|

2020

|

Vol. 174, nr 3/4

311--344

EN

Algorithms based on singleton arc consistency (SAC) show considerable promise for improving backtrack search algorithms for constraint satisfaction problems (CSPs). The drawback is that even the most efficient of them is still comparatively expensive. Even when limited to preprocessing, they give overall improvement only when problems are quite difficult to solve with more typical procedures such as maintained arc consistency (MAC). The present work examines a form of partial SAC and neighbourhood SAC (NSAC) in which a subset of the variables in a CSP are chosen to be made SAC-consistent or neighbourhood-SAC-consistent. Such consistencies, despite their partial character, are still well-characterized in that algorithms have unique fixpoints. Heuristic strategies for choosing an effective subset of variables are described and tested, the best being choice by highest degree and a more complex strategy of choosing by constraint weight after random probing. Experimental results justify the claim that these methods can be nearly as effective as the corresponding full version of the algorithm in terms of values discarded or problems proven unsatisfiable, while significantly reducing the effort required to achieve this.

4

Candidate Selection and Instance Ordering for Realtime Algorithm Configuration

Fitzgerald Tadhg, O'Sullivan Barry

Fundamenta Informaticae

|

2019

|

Vol. 166, nr 2

141--166

EN

Many modern combinatorial solvers have a variety of parameters through which a user can customise their behaviour. Algorithm configuration is the process of selecting good values for these parameters in order to improve performance. Time and again algorithm configuration has been shown to significantly improve the performance of many algorithms for solving challenging computational problems. Automated systems for tuning parameters regularly out-perform human experts, sometimes but orders of magnitude. Online algorithm configurators, such as ReACTR, are able to tune a solver online without incurring costly offline training. As such ReACTR’s main focus is on runtime minimisation while solving combinatorial problems. To do this ReACTR adopts a one-pass methodology where each instance in a stream of instances to be solved is considered only as it arrives. As such ReACTR’s performance is sensitive to the order in which instances arrive. It is still not understood which instance orderings positively or negatively effect the performance of ReACTR. This paper investigates the effect of instance ordering and grouping by empirically evaluating different instance orderings based on difficulty and feature values. Though the end use is generally unable to control the order in which instances arrive it is important to understand which orderings impact Re-ACTR’s performance and to what extent. This study also has practical benefit as such orderings can occur organically. For example as business grows the problems it may encounter, such as routing or scheduling, often grow in size and difficulty. ReACTR’s performance also depends strongly configuration selection procedure used. This component controls which configurations are selected to run in parallel from the internal configuration pool. This paper evaluates various ranking mechanisms and different ways of combining them to better understand how the candidate selection procedure affects realtime algorithm configuration. We show that certain selection procedures are superior to others and that the order which instances arrive in determines which selection procedure performs best. We find that both instance order and grouping can significantly affect the overall solving time of the online automatic algorithm configurator ReACTR. One of the more surprising discoveries is that having groupings of similar instances can actually negatively impact on the overall performance of the configurator. In particular we show that orderings based on nearly any instance feature values can lead to significant reductions in total runtime over random instance orderings. In addition, certain candidate selection procedures are more suited to certain orderings than others and selecting the correct one can show a marked improvement in solving times.

5

Reasoning on Datalog± Ontologies with Abductive Logic Programming

Gavanelli M., Lamma E., Riguzzi F., Bellodi E., Zese R., Cota G.

Fundamenta Informaticae

|

2018

|

Vol. 159, nr 1/2

65--93

EN

Ontologies form the basis of the Semantic Web. Description Logics (DLs) are often the languages of choice for modeling ontologies. Integration of DLs with rules and rule-based reasoning is crucial in the so-called Semantic Web stack vision - a complete stack of recommendations and languages each based on and/or exploiting the underlying layers - which adds new features to the standards used in the Web. The growing importance of the integration between DLs and rules is proved by the definition of the profile OWL 2 RL1 and the definition of languages such as RIF2 and SWRL3. Datalog± is an extension of Datalog which can be used for representing lightweight ontologies and expressing some languages of the DL-Lite family, with tractable query answering under certain language restrictions. In particular, it is able to express the DL-Lite version defined in OWL. In this work, we show that Abductive Logic Programming (ALP) can be used to represent Datalog± ontologies, supporting query answering through an abductive proof procedure, and smoothly achieving the integration of ontologies and rule-based reasoning. Often, reasoning with DLs means finding explanations for the truth of queries, that are useful when debugging ontologies and to understand answers given by the reasoning process. We show that reasoning under existential rules can be expressed by ALP languages and we present a solving system, which is experimentally proved to be competitive with DL reasoning systems. In particular, we consider an ALP framework named SCIFF derived from the IFF abductive framework. Forward and backward reasoning is naturally supported in this ALP framework. The SCIFF language smoothly supports the integration of rules, expressed in a Logic Programming language, with Datalog± ontologies, mapped into SCIFF (forward) integrity constraints. The main advantage is that this integration is achieved within a single language, grounded on abduction in computational logic, and able to model existential rules.

6

Answer Set Programming Modulo Acyclicity

Bomanson J., Janhunen T., Schaub T., Gebser M., Kaufmann B.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 1

63--91

EN

Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the stateof- the-art ASP solver CLASP. The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving.

7

A new approach to hull consistency

Kolev L.

Archives of Electrical Engineering

|

2016

|

Vol. 65, nr 2

305--314

EN

Hull consistency is a known technique to improve the efficiency of iterative interval methods for solving nonlinear systems describing steady-states in various circuits. Presently, hull consistency is checked in a scalar manner, i.e. successively for each equation of the nonlinear system with respect to a single variable. In the present poster, a new more general approach to implementing hull consistency is suggested which consists in treating simultaneously several equations with respect to the same number of variables.

8

A Secure Non-monotonic Soft Concurrent Constraint Language

Bistarelli S., Santini F.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 3/4

261--285

EN

We present a fine-grained security model to enforce the access control on the shared constraint store in Concurrent Constraint Programming (CCP) languages. We show the model for a non-monotonic version of Soft CCP (SCCP), that is an extension of CCP where the constraints have a preference level associated with them. Crisp constraints can be modeled in the same framework as well. In the considered non-monotonic soft version (NmSCCP), it is also possible to remove constraints from the store. The language can be used for coordinating agents on a common store of information that represents the set of shared resources. In such scenarios, it is clearly important to enforce the integrity and confidentiality rights on the resources, in order, for instance, to hide part of the information to some agents, or to prevent an agent to consume too many resources. Finally, we present a bisimulation relation to check equivalence between two programs written in this language.

9

Planowanie rozmieszczenia ruchomych podpór jako dyskretny problem spełniania ograniczeń

Szynkiewicz W., Kasprzak W., Zielinska T.

Pomiary Automatyka Robotyka

|

2012

|

R. 16, nr 2

344-350

PL

W pracy przedstawiono koncepcję układu planowania (planera) dla samoadaptowalnego i rekonfigurowalnego systemu mocowań-podpór dla cienkościennych przedmiotów (blach) o dużych rozmiarach w procesie obróbczym polegającym na frezowaniu i wierceniu otworów. W proponowanym rozwiązaniu system mocowań-podpór składa się z ławy oraz ruchomych agentów - manipulatorów mobilnych. Zadaniem planera jest wygenerowanie sekwencji wykonalnych pozycji dla każdego agenta spełniających ograniczenia geometryczne i czasowe. Struktura planera ścieżki, zwanego "potrójnym CSP", składa się z trójpoziomowej hierarchii problemów przeszukiwania dyskretnych przestrzeni rozwiązań. Do rozwiązania zadania planowania ścieżki dla głowic, ruchomych baz i manipulatorów równoległych, stanowiących części mobilnych agentów-podpór, zastosowano sterowany ograniczeniami algorytm przeszukiwania z nawrotami. W pracy przedstawiono projekt i implementację planera oraz omówiono przykładowe plany wyznaczone dla operacji frezowania i wiercenia otworów.

EN

The paper presents a planner module of a self-reconfigurable fixture system needed in the machining of thin-sheet large work-parts, namely milling and hole drilling processes. The proposed system consists of a power-supplying bench and two or more mobile robotic agents. The objective is to create an action plan for the positioning and reconfiguring of two or more mobile robotic fixtures that satisfies geometric and time-related constraints. The path planner structure, called Triple-CSP, consists of three levels of constraint satisfaction search. We propose an incremental, constraint-driven backtracking search to solve three hierarchic path planning tasks: for the supporting heads, the mobile bases, and the Parallel Kinematic Machine configurations of the mobile fixtures. The paper concentrates on the planner design and implementation and shows example plans obtained for milling and hole drilling processes.

10

Approaches to the production flow scheduling and control

Skołud B.

Journal of Machine Engineering

|

2008

|

Vol. 8, No. 2

5--13

EN

In the paper different methods of production order scheduling and control that are elaborated by the author and the team are presented. The history starts from the dispatching rules and goes to the distributed control by the local dispatching rule allocation and application them in the software (KbRS, SWZ, etc). In the next stage of the paper the discussion goes to the integration of these approaches. Last stage of the paper the artificial intelligence (Immune Algorithm) application for optimization of the schedule under the condition that any permissible solution is attainable is proposed. This application is only the part of the integrated system and is utilized as a tool for the solution improvement.

11

Constraint satisfaction techniques in planning and scheduling: An introduction

Bartak R.

Archives of Control Sciences

|

2008

|

Vol. 18, no. 2

141-158

EN

Planning and scheduling are two closely related areas that, despite their similarity, deal with different problems. While the planning ask is to decide which actions are necessary to achieve a given goal, the scheduling task is to allocate known activities to scarce resources, such as machines, over time. Typically planning and scheduling problems are solved separately using different solving techniques. However, real-life problems require a more integrated approach. Constraint satisfaction seems to be such a unifying solving technology for both planning and scheduling problems. This paper describes how constraint satisfaction techniques can be applied to planning and scheduling problems.

12

CuikSLAM with unknown correspondence - preliminary results

Kubica B., Szynkiewicz W.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2007

|

z. 160

143-151

EN

This paper considers the problem of simultaneous localization and mapping of a mobile robot. The kinematic approach of CuikSLAM is adopted applying constrained satisfaction and interval methods. The novelty is that we do not assume the landmark identification problem to br solved.

13

Constraint models for complex state transitions

Barták R.

Computer Assisted Mechanics and Engineering Sciences

|

2007

|

Vol. 14, No. 4

543-555

EN

Constraint-based scheduling is an approach for solving real-life scheduling problems by combining the generality of AI techniques with the efficiency of OR techniques. Basically, it describes a scheduling problem as a constraint satisfaction problem and then uses constraint satisfaction techniques to find a solution. In this paper we study three constraint models describing complex state transitions that are going beyond the existing models of resources (machines) used in scheduling. These models can naturally handle any setup/changeover/transition scheme as well as special counter constraints imposed on the sequence of activities. The proposed models have been implemented and tested in the commercial scheduling engine of Visopt ShopFloor system.

14

Emergent problem solving in multi-agent systems

Quinqueton J.

Zeszyty Naukowe Uniwersytetu Jagiellońskiego. Prace Informatyczne

|

2000

|

z. 10

147-163

EN

Problem solving with multi-agent systems appears to be a very active research area nowadays. We present in this talk an overview of some works around distributed Constraint Satisfaction Problems and we point out some recent results about phase transition and emergence in multi-agents resolution of such problems. We also point out the links and differences with distributed or randomized algorithms.