Insight Centre for Data Analytics - Journal Articles

Permanent URI for this collection

https://hdl.handle.net/10468/5058

Browse

Now showing 1 - 20 of 98

Influence of noise intensity on the spectrum of an oscillator
(IEEE, 2005-11) Swain, Rabi Sankar; Gleeson, James P.; Kennedy, Michael Peter; Science Foundation Ireland; Analog Devices
This paper investigates the influence of high-intensity noise on the correlation spectrum of a two-dimensional (2-D) nonlinear oscillator. An exact analytical solution for the correlation spectrum of this 2-D oscillator is provided. The analytical derivations are well suited for oscillators with white noise of any intensity, but computational constraints on the solution of the partial differential equation may make it impractical for cases where the number of state variables exceeds three. The spectral results predicted by our analytical method are verified by numerical simulations of the noisy oscillator in the time domain. We find that the peak of the oscillator spectrum shifts toward higher frequencies as the noise intensity is increased, as opposed to the fixed oscillation frequency predicted in the existing literature. This phenomenon does not appear to have been reported previously in the context of phase noise in oscillators.
A logic of soft constraints based on partially ordered preferences
(Springer, 2006-06) Wilson, Nic; Science Foundation Ireland; European Commission
Representing and reasoning with an agent's preferences is important in many applications of constraints formalisms. Such preferences are often only partially ordered. One class of soft constraints formalisms, semiring-based CSPs, allows a partially ordered set of preference degrees, but this set must form a distributive lattice; whilst this is convenient computationally, it considerably restricts the representational power. This paper constructs a logic of soft constraints where it is only assumed that the set of preference degrees is a partially ordered set, with a maximum element 1 and a minimum element 0. When the partially ordered set is a distributive lattice, this reduces to the idempotent semiring-based CSP approach, and the lattice operations can be used to define a sound and complete proof theory. A generalised possibilistic logic, based on partially ordered values of possibility, is also constructed, and shown to be formally very strongly related to the logic of soft constraints. It is shown how the machinery that exists for the distributive lattice case can be used to perform sound and complete deduction, using a compact embedding of the partially ordered set in a distributive lattice.
Proactive algorithms for job shop scheduling with probabilistic durations
(Association for the Advancement of Artificial Intelligence (AAAI), 2007-07) Beck, J. Christopher; Wilson, Nic; Science Foundation Ireland
Most classical scheduling formulations assume a fixed and known duration for each activity. In this paper, we weaken this assumption, requiring instead that each duration can be represented by an independent random variable with a known mean and variance. The best solutions are ones which have a high probability of achieving a good makespan. We first create a theoretical framework, formally showing how Monte Carlo simulation can be combined with deterministic scheduling algorithms to solve this problem. We propose an associated deterministic scheduling problem whose solution is proved, under certain conditions, to be a lower bound for the probabilistic problem. We then propose and investigate a number of techniques for solving such problems based on combinations of Monte Carlo simulation, solutions to the associated deterministic problem, and either constraint programming or tabu search. Our empirical results demonstrate that a combination of the use of the associated deterministic problem and Monte Carlo simulation results in algorithms that scale best both in terms of problem size and uncertainty. Further experiments point to the correlation between the quality of the deterministic solution and the quality of the probabilistic solution as a major factor responsible for this success.
The computational complexity of dominance and consistency in CP-Nets
(Association for the Advancement of Artificial Intelligence (AAAI), 2008-03) Goldsmith, Judy; Lang, Jerome; Truszczynski, Miroslaw; Wilson, Nic; Science Foundation Ireland
We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas..
Semiring induced valuation algebras: Exact and approximate local computation algorithms
(Elsevier, 2008-07) Kohlas, Juerg; Wilson, Nic; Science Foundation Ireland
Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra. There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.
Extending uncertainty formalisms to linear constraints and other complex formalisms
(Elsevier, 2008-08) Wilson, Nic; Science Foundation Ireland
Linear constraints occur naturally in many reasoning problems and the information that they represent is often uncertain. There is a difficulty in applying AI uncertainty formalisms to this situation, as their representation of the underlying logic, either as a mutually exclusive and exhaustive set of possibilities, or with a propositional or a predicate logic, is inappropriate (or at least unhelpful). To overcome this difficulty, we express reasoning with linear constraints as a logic, and develop the formalisms based on this different underlying logic. We focus in particular on a possibilistic logic representation of uncertain linear constraints, a lattice-valued possibilistic logic, an assumption-based reasoning formalism and a Dempster-Shafer representation, proving some fundamental results for these extended systems. Our results on extending uncertainty formalisms also apply to a very general class of underlying monotonic logics.
Conditional lexicographic orders in constraint satisfaction problems
(Springer, 2009-09) Wallace, Richard J.; Wilson, Nic; Science Foundation Ireland
The lexicographically-ordered CSP ("lexicographic CSP" or "LO-CSP" for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to a given variable is more important than any change in assignment to any less important variable. In this paper, we show how this representation can be extended to handle conditional preferences in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the importance ordering of variables. In this case, by obviating the "overwhelming advantage" effect with respect to the original variables and values, the representational capacity is significantly enhanced. For problems of the first type, any of the algorithms originally devised for ordinary LO-CSPs can also be used when some of the domain orderings are dependent on assignments to "parent" variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary LO-CSPs can be extended to handle CSPs with conditional domain orderings.
Interleaving solving and elicitation of constraint satisfaction problems based on expected cost
(Springer, 2010-01) Wilson, Nic; Grimes, Diarmuid; Freuder, Eugene C.; Science Foundation Ireland
We consider Constraint Satisfaction Problems in which constraints can be initially incomplete, where it is unknown whether certain tuples satisfy the constraint or not. We assume that we can determine the satisfaction of such an unknown tuple, i.e., find out whether this tuple is in the constraint or not, but doing so incurs a known cost, which may vary between tuples. We also assume that we know the probability of an unknown tuple satisfying a constraint. We define algorithms for this problem, based on backtracking search. Specifically, we consider a simple iterative algorithm based on a cost limit on the unknowns that may be determined, and a more complex algorithm that delays determining an unknown in order to estimate better whether doing so is worthwhile. We show experimentally that the more sophisticated algorithms can greatly reduce the average cost.
Enabling local computation for partially ordered preferences
(Springer, 2010-01) Fargier, Hélène; Rollon, Emma; Wilson, Nic; Science Foundation Ireland
Many computational problems linked to uncertainty and preference management can be expressed in terms of computing the marginal(s) of a combination of a collection of valuation functions. Shenoy and Shafer showed how such a computation can be performed using a local computation scheme. A major strength of this work is that it is based on an algebraic description: what is proved is the correctness of the local computation algorithm under a few axioms on the algebraic structure. The instantiations of the framework in practice make use of totally ordered scales. The present paper focuses on the use of partially ordered scales and examines how such scales can be cast in the Shafer-Shenoy framework and thus benefit from local computation algorithms. It also provides several examples of such scales, thus showing that each of the algebraic structures explored here is of interest.
Lexicographically-ordered constraint satisfaction problems
(Springer, 2010-01) Freuder, Eugene C.; Heffernan, Robert; Wallace, Richard J.; Wilson, Nic; Science Foundation Ireland
We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character, these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of heuristics that follow the preference order (lexical variable and value ordering). We describe relations between lexicographic CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter. We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms: a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including some for which the basic lexically ordered search is infeasible in practice.
Interval-valued soft constraint problems
(Springer-Verlag, 2010-04) Gelain, Mirco; Pini, Maria Silvia; Rossi, Francesca; Venable, Kristin Brent; Wilson, Nic; Science Foundation Ireland; Ministero dell’Istruzione, dell’Università e della Ricerca, Italy
Constraints and quantitative preferences, or costs, are very useful for modelling many real-life problems. However, in many settings, it is difficult to specify precise preference values, and it is much more reasonable to allow for preference intervals. We define several notions of optimal solutions for such problems, providing algorithms to find optimal solutions and also to test whether a solution is optimal. Most of the time these algorithms just require the solution of soft constraint prob- lems, which suggests that it may be possible to handle this form of uncertainty in soft constraints without significantly increasing the computational effort needed to reason with such problems. This is supported also by experimental results. We also identify classes of problems where the same results hold if users are allowed to use multiple disjoint intervals rather than a single one.
Developing approaches for solving a telecommunications feature subscription problem
(AI Access Foundation, 2010-06) Lesaint, David; Mehta, Deepak; O'Sullivan, Barry; Quesada, Luis; Wilson, Nic; Science Foundation Ireland
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. The configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation, which is a generalisation of the feedback vertex set problem on directed graphs, and thus it is an NP-hard task. We present several constraint programming formulations of the problem. We also present formulations using partial weighted maximum Boolean satisfiability and mixed integer linear programming. We study all these formulations by experimentally comparing them on a variety of randomly generated instances of the feature subscription problem.
Preference dominance reasoning for conversational recommender systems: a comparison between a comparative preferences and a sum of weights approach
(World Scientific Publishing Company, 2011) Trabelsi, Walid; Wilson, Nic; Bridge, Derek G.; Ricci, Francesco; Science Foundation Ireland
A conversational recommender system iteratively shows a small set of options for its user to choose between. In order to select these options, the system may analyze the queries tried by the user to derive whether one option is dominated by others with respect to the user's preferences. The system can then suggest that the user try one of the undominated options, as they represent the best options in the light of the user preferences elicited so far. This paper describes a framework for preference dominance. Two instances of the framework are developed for query suggestion in a conversational recommender system. The first instance of the framework is based on a basic quantitative preferences formalism, where options are compared using sums of weights of their features. The second is a qualitative preference formalism, using a language that generalises CP-nets, where models are a kind of generalised lexicographic order. A key feature of both methods is that deductions of preference dominance can be made efficiently, since this procedure needs to be applied for many pairs of options. We show that, by allowing the recommender to focus on undominated options, which are ones that the user is likely to be contemplating, both approaches can dramatically reduce the amount of advice the recommender needs to give to a user compared to what would be given by systems without this kind of reasoning.
Computational techniques for a simple theory of conditional preferences
(Elsevier, 2011-05) Wilson, Nic; Science Foundation Ireland
A simple logic of conditional preferences is defined, with a language that allows the compact representation of certain kinds of conditional preference statements, a semantics and a proof theory. CP-nets and TCP-nets can be mapped into this logic, and the semantics and proof theory generalise those of CP-nets and TCP-nets. The system can also express preferences of a lexicographic kind. The paper derives various sufficient conditions for a set of conditional preferences to be consistent, along with algorithmic techniques for checking such conditions and hence confirming consistency. These techniques can also be used for totally ordering outcomes in a way that is consistent with the set of preferences, and they are further developed to give an approach to the problem of constrained optimisation for conditional preferences.
Restoring wireless sensor network connectivity in damaged environments
(Elsevier, 2012-08-09) Truong, Thuy T.; Brown, Kenneth N.; Sreenan, Cormac J.; Higher Education Authority
A wireless sensor network can become partitioned due to node failure, requiring the deployment of additional relay nodes in order to restore network connectivity. This introduces an optimisation problem involving a tradeoff between the number of additional nodes that are required and the costs of moving through the sensor field for the purpose of node placement. This tradeoff is application-dependent, influenced for example by the relative urgency of network restoration. We propose four heuristic algorithms which integrate network design with path planning, recognising the impact of obstacles on mobility and communication. We conduct an empirical evaluation of the four algorithms on random connectivity and mobility maps, showing their relative performance in terms of node and path costs, and assessing their execution speeds. Finally, we examine how the relative importance of the two objectives influences the choice of algorithm.
Repairing Wireless Sensor Network connectivity with mobility and hop-count constraints
(Springer Verlag, 2013-07) Truong, Thuy T.; Brown, Kenneth N.; Sreenan, Cormac J.; Cichoń, J.; Gȩbala, M.; Klonowski, M.; Higher Education Authority; Science Foundation Ireland
Wireless Sensor Networks can become partitioned due to node failure or damage, and must be repaired by deploying new sensors, relays or sink nodes to restore some quality of service. We formulate the task as a multi-objective problem over two graphs. The solution specifies additional nodes to reconnect a connectivity graph subject to network path-length constraints, and a path through a mobility graph to visit those locations. The objectives are to minimise both the cost of the additional nodes and the length of the mobility path. We propose two heuristic algorithms which prioritise the different objectives. We evaluate the two algorithms on randomly generated graphs, and compare their solutions to the optimal solutions for the individual objectives. Finally, we assess the total restoration time for different classes of agent, i.e. small robots and larger vehicles, which allows us to trade-off longer computation times for shorter mobility paths.
Robustness and stability in Constraint Programming under dynamism and uncertainty
(AI Access Foundation, 2014-01-28) Climent, Laura; Wallace, Richard J.; Salido, Miguel A.; Barber, Frederico; Ministerio de Ciencia e Innovación
Many real life problems that can be solved by constraint programming, come from uncertain and dynamic environments. Because of the dynamism, the original problem may change over time, and thus the solution found for the original problem may become invalid. For this reason, dealing with such problems has become an important issue in the fields of constraint programming. In some cases, there exist extant knowledge about the uncertain and dynamic environment. In other cases, this information is fragmentary or unknown. In this paper, we extend the concept of robustness and stability for Constraint Satisfaction Problems (CSPs) with ordered domains, where only limited assumptions need to be made as to possible changes. We present a search algorithm that searches for both robust and stable solutions for CSPs of this nature. It is well-known that meeting both criteria simultaneously is a desirable objective for constraint solving in uncertain and dynamic environments. We also present compelling evidence that our search algorithm outperforms other general-purpose algorithms for dynamic CSPs using random instances and benchmarks derived from real life problems.
Cognitive radio for disaster response networks: survey, potential, and challenges
(IEEE, 2014-10-31) Ghafoor, Saim; Sutton, Paul D.; Sreenan, Cormac J.; Brown, Kenneth N.; Science Foundation Ireland
In the wake of a natural or man-made disaster, restoration of telecommunications is essential. First responders must coordinate their responses, immediate casualties require assistance, and all affected citizens may need to access information and contact friends and relatives. Existing access and core infrastructure may be damaged or destroyed, so to support the required services, new infrastructure must be rapidly deployed and integrated with undamaged resources still in place. This new equipment should be flexible enough to interoperate with legacy systems and heterogeneous technologies. The ability to selforganize is essential in order to minimize any delays associated with manual configuration. Finally, it must be robust and reliable enough to support mission-critical applications. Wireless systems can be more easily reconfigured than wired solutions to adapt to the various changes in the operating environment that can occur in a disaster scenario. A cognitive radio is one that can observe its operating environment, make decisions and reconfigure in response to these observations, and learn from experience. This article examines the use of cognitive radio technologies for disaster response networks and shows that they are ideally suited to fulfill the unique requirements of these networks. Key enabling technologies for realizing real-world cognitive radio networks for disaster response are discussed and core challenges are examined.
A constraint programming approach to the additional relay placement problem in Wireless Sensor Networks
(Springer, 2015-04-02) Sitanayah, Lanny; Brown, Kenneth N.; O'Sullivan, Barry; Sreenan, Cormac J.; Quesada, Luis; Science Foundation Ireland
A Wireless Sensor Network (WSN) is composed of many sensor nodes which transmit their data wirelessly over a multi-hop network to data sinks. Since WSNs are subject to node failures, the network topology should be robust, so that when a failure does occur, data delivery can continue from all surviving nodes. A WSN is k-robust if an alternate length-constrained route to a sink is available for each surviving node after the failure of up to k-1 nodes. A WSN is strongly k-robust if there are k disjoint length-constrained routes to a sink for each node. Determining whether a network is k-robust is polynomial. However, determining whether a network is strongly k-robust is an NP-complete problem. We develop a Constraint Programming (CP) approach for deciding strongly k-robustness that outperforms a Mixed-Integer Programming (MIP) model on larger problems. A network can be made (strongly) robust by deploying extra relay nodes. We extend our CP approach to an optimisation approach by using QuickXplain to search for a minimal set of relays, and compare it to a state-of-the-art local search approach.
Multi-objective hierarchical algorithms for restoring Wireless Sensor Network connectivity in known environments
(Elsevier, 2015-05-15) Truong, Thuy T.; Brown, Kenneth N.; Sreenan, Cormac J.; Higher Education Authority; Science Foundation Ireland
A Wireless Sensor Network can become partitioned due to node failure, requiring the deployment of additional relay nodes in order to restore network connectivity. This introduces an optimisation problem involving a tradeoff between the number of additional nodes that are required and the costs of moving through the sensor field for the purpose of node placement. This tradeoff is application-dependent, influenced for example by the relative urgency of network restoration. We propose a family of algorithms based on hierarchical objectives including complete algorithms and heuristics which integrate network design with path planning, recognising the impact of obstacles on mobility and communication. We conduct an empirical evaluation of the algorithms on random connectivity and mobility graphs, showing their relative performance in terms of node and path costs, and assessing their execution speeds. Finally, we examine how the relative importance of the two objectives influences the choice of algorithm. In summary, the algorithms which prioritise the node cost tend to find graphs with fewer nodes, while the algorithm which prioritise the cost of moving find slightly larger solutions but with cheaper mobility costs. The heuristic algorithms are close to the optimal algorithms in node cost, and higher in mobility costs. For fast moving agents, the node algorithms are preferred for total restoration time, and for slow agents, the path algorithms are preferred.

Browse

Browsing Insight Centre for Data Analytics - Journal Articles by Issue Date

Results Per Page

Sort Options