Wyniki wyszukiwania - BazTech

1

An Experimental Study of Influence of Modeling and Solving Techniques on Performance of a Tabled Logic Programming Planner

Barták R., Vodrážka J.

Fundamenta Informaticae

|

2016

|

Vol. 149, nr 1/2

35--60

EN

Logic programming provides a declarative framework for modeling and solving many combinatorial problems. Until recently, it was not competitive with state-of-the-art planning techniques partly due to search capabilities limited to backtracking. Recent development brought more advanced search techniques to logic programming such as tabling that simplifies implementation and exploitation of more sophisticated search algorithms. Together with rich modeling capabilities this progress brings tabled logic programing on a par with current best planners. This paper describes the planner module of the tabled logic programming language Picat, its modeling capabilities, and core search procedures behind the planner. The major contribution is an experimental comparison of the influence of various modeling techniques, namely factored vs. structured representations of states, control knowledge, and heuristics on the performance of two search procedures – iterative deepening and branch and bound-behind the planner. The paper also compares the Picat planner with winning automated planners both domain dependent and domain independent to demonstrate that the presented techniques are competitive with state-of-the-art.

2

Algorytm branch-and-bound dla pewnego problemu szeregowania zadań uwarunkowanych czasowo

Ocetkiewicz K. M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2009

|

T. 13, z. 2

521-529

PL

W pracy przedstawiono algorytm branch-and-bound dla problemu szeregowania zadań uwarunkowanych czasowo 1 | pi = 1 + atst | XQ, a także wyniki eksperymentów komputerowych prezentujących wydajność algorytmu. Zastosowanie przedstawionego algorytmu umożliwia powiększenie "obliczalnych" rozmiarów instancji o 6-10 zadań w stosunku do algorytmu pełnego przeszukiwania.

EN

The article presents a branch-and-bound algorithm for a following time-dependent scheduling problem: 1 \pt: = 1 + atst | XC,. The computational experiments were conducted to examine the efficiency of the algorithm. Application of the presented algorithm allows us to increase the size of input instances that can be solved to optimality in reasonable time by 6-10 jobs, compared to the exhaustive-search algorithm.

3

Configuring a sensor network for fault detection in distributed parameter systems

Patan M., Uciński D.

International Journal of Applied Mathematics and Computer Science

|

2008

|

Vol. 18, no. 4

513-524

EN

The problem of fault detection in distributed parameter systems (DPSs) is formulated as that of maximizing the power of a parametric hypothesis test which checks whether or not system parameters have nominal values. A computational scheme is provided for the design of a network of observation locations in a spatial domain that are supposed to be used while detecting changes in the underlying parameters of a distributed parameter system. The setting considered relates to a situation where from among a finite set of potential sensor locations only a subset can be selected because of the cost constraints. As a suitable performance measure, the Ds-optimality criterion defined on the Fisher information matrix for the estimated parameters is applied. Then, the solution of a resulting combinatorial problem is determined based on the branch-and-bound method. As its essential part, a relaxed problem is discussed in which the sensor locations are given a priori and the aim is to determine the associated weights, which quantify the contributions of individual gauged sites. The concavity and differentiability properties of the criterion are established and a gradient projection algorithm is proposed to perform the search for the optimal solution. The delineated approach is illustrated by a numerical example on a sensor network design for a two-dimensional convective diffusion process.

4

Task allocation algorithms for maximizing reliability of heterogeneous distributed computing systems

Mahmood A.

Control and Cybernetics

|

2001

|

Vol. 30, no. 1

115-130

EN

The rapid progress of microprocessor and communication technologies has made the distributed computing system economically attractive for many computer applications. One of the first problems encountered in the operation of a distributed system is the problem of allocating the tasks among the processing nodes. The task allocation problem is known to be computationally intractable for large task sets. In this paper, we consider the task allocation problem with the goal of maximizing reliability of heterogeneous distributed systems. After presenting a quantitative task allocation model, we present a least-cost branch-and-bound algorithm to find optimal task allocations. We also present two heuristic algorithms to obtain suboptimal allocations for realistic size large problems in a reasonable amount of computational time. Simulation was used to study the performance of the proposed algorithms for a large number of problems. Also, performance of the proposed algorithms has been compared with a well-known heuristics available in the literature.