Antichains and compositional algorithms for LTL synthesis

In this paper, we present new monolithic and compositional algorithms to solve the LTL realizability problem. Those new algorithms are based on a reduction of the LTL realizability problem to a game whose winning condition is defined by a universal automaton on infinite words with a k-co-Büchi acceptance condition. This acceptance condition asks that runs visit at most k accepting states, so it implicitly defines a safety game. To obtain efficient algorithms from this construction, we need several additional ingredients. First, we study the structure of the underlying automata constructions, and we show that there exists a partial order that structures the state space of the underlying safety game. This partial order can be used to define an efficient antichain algorithm. Second, we show that the algorithm can be implemented in an incremental way by considering increasing values of k in the acceptance condition. Finally, we show that for large LTL formulas that are written as conjunctions of smaller formulas, we can solve the problem compositionally by first computing winning strategies for each conjunct that appears in the large formula. We report on the behavior of those algorithms on several benchmarks. We show that the compositional algorithms are able to handle LTL formulas that are several pages long.     

Objective selection of suitable unit cell size in data-driven modeling of mineral prospectivity

In GIS-based data-driven modeling of mineral prospectivity, a suitably fine unit cell size is used for spatial representation of known occurrences of mineral deposits of the type sought (D) in a study area (T). However, until now, the unit cell size is chosen subjectively. In this paper, a methodology is proposed for objective selection of the most suitable unit cell size for data-driven modeling of mineral prospectivity using a raster-based GIS. A set of choices of suitable unit cell sizes is first derived via point pattern analysis of a set of known occurrences of mineral deposits of the type sought. Then, (a) the lower limit of a set of choices of suitable unit cell sizes is considered and defined according to the map scales from which spatial data for mineral prospectivity mapping were derived, and (b) the upper limit of the same set of choices of suitable unit cell sizes is considered (and revised as necessary) based on knowledge of spatial extents of mineral deposits of the type sought or via analysis of reflexive nearest neighbour points. Finally, it is shown that fractal analysis of spatial contrast between unit cells containing D and unit cells not containing D in T provides for objective selection of the most suitable unit cell size. In a case study application of the weight-of-evidence method to mineral prospectivity mapping, using the most suitable unit cell size, found via the proposed methodology, results in spatial evidence weights and weight uncertainties that are nearly identical to those derived by using the finest (i.e., lower limit) unit cell size. In contrast to using the most suitable unit cell size, using coarser unit cell sizes result in higher positive weights, lower negative weights and higher weight uncertainties of spatial evidence of mineral prospectivity. The proposed methodology for objective selection of the most suitable unit cell size in data-driven modeling of mineral prospectivity using a raster-based GIS is robust and can easily be implemented.     

Tool path smoothing of a redundant machine: Application to Automated Fiber Placement

Automated Tape Laying and Fiber Placement of composite materials are the two principal automated processes used for fabrication of large composite structures in aeronautical industry. The aluminum parts produced by High Speed Machining tend to be replaced by carbon fiber composite parts realized with these processes. However, structural parts present reinforcement zones which disturb the tool path follow-up and generate an increase of the manufacturing time. Thus, this paper deals with the optimization of tool paths of a 7-axis machine tool of Fiber Placement with the objective of reducing the manufacturing time while ensuring the requested quality of the final part. In this paper, two complementary methods are detailed. The first method takes advantage of the degree of redundancy of the machine tool to decrease the kinematic loads of the control joints. The second method aims to smooth the orientation of the machine head along the tool path while ensuring quality constraints. These two methods are then applied on a test tool path and bring to a significant decrease of the manufacturing time (32.9%).     

Evaluating increasing block tariff pricing policies when applied to multiple household connections

This paper develops a model for evaluating the consequences of increasing block tariff pricing policies when multiple households share a connection and applies it to a sample from Kumasi, Ghana. Results show that for any given consumption, a household's average share of total monthly water bill for shared connections can either be higher or lower than its single-household equivalent. Significant differences between the average and single-household equivalent bills were found in these cases, although this difference is under-estimated if the sample is not disaggregated by payment group.     

Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem

We present new and effective lower bounds for the resource constrained project scheduling problem. This problem is widely known to be notoriously difficult to solve due to the lack of lower bounds that are both tight and fast. In this paper, we propose several new lower bounds that are based on the concept of energetic reasoning. A major contribution of this work is to investigate several enhanced new feasibility tests that prove useful for deriving new lower bounds that consistently outperform the classical energetic reasoning-based lower bound. In particular, we present the results of a comprehensive computational study, carried out on 1560 benchmark instances, that provides strong evidence that a deceptively simple dual feasible function-based lower bound is highly competitive with a state-of-the-art lower bound while being extremely fast. Furthermore, we found that an effective shaving procedure enables to derive an excellent lower bound that often outperforms the best bound from the literature while being significantly simpler.     

Privacy enabled video surveillance using a two state Markov tracking algorithm

Nowadays video surveillance systems are widely deployed in many public places. However, the widespread use of video surveillance violates the privacy rights of the people. Many authors have addressed the privacy issues from various points of view. In this paper we propose a novel, on-demand selectively revocable, privacy preserving mechanism. The surveillance video can be tuned to view with complete privacy or by revoking the privacy of any subset of pedestrians while ensuring complete privacy to the remaining pedestrians. We achieve this by tracking the pedestrians using a novel Markov chain algorithm with two hidden states, detecting the head contour of the tracked pedestrians and obscuring their faces using an encryption mechanism. The detected pedestrian face/head is obscured by encrypting with a unique key derived from a master key for the privacy preservation purpose. The performance evaluations on many challenging surveillance scenarios show that the proposed mechanism can effectively and robustly track as well as identify multiple pedestrians and obscure/unobscure their faces/head in real time.     

Recognition of Simple Enlarged Horn Formulas and Simple Extended Horn Formulas

The enlarged Horn formulas generalize the extended Horn formulas introduced by Chandru and Hooker (1991). Their satisfying truth assignments can be generated with polynomial delay. Unfortunately no polynomial algorithm is known for recognizing enlarged Horn formulas or extended Horn formulas. In this paper we define the class of simple enlarged Horn formulas, a subclass of the enlarged Horn formulas, that contains the simple extended Horn formulas introduced by Swaminathan and Wagner (1995). We present recognition algorithms for the simple enlarged Horn formulas and the simple extended Horn formulas whose complexity is bounded by the complexity of the arborescence-realization problem.     

Direction relations and two-dimensional range queries: optimisation techniques

This paper defines direction relations (e.g., north, northeast) between two-dimensional objects and shows how they can be efficiently retrieved using B-, KDB- and R- tree-based data structures. Essentially, our work studies optimisation techniques for 2D range queries that arise during the processing of direction relations. We test the efficiency of alternative indexing methods through extensive experimentation and present analytical models that estimate their performance. The analytical estimates are shown to be very close to the actual results and can be used by spatial query optimizers in order to predict the retrieval cost. In addition, we implement modifications of the existing structures that yield better performance for certain queries. We conclude the paper by discussing the most suitable method depending on the type of the range and the properties of the data.