Computer Science - Journal Articles

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 175

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.
Worst-case delay control in multigroup overlay networks
(IEEE, 2007-10) Tu, Wanqing; Sreenan, Cormac J.; Jia, Weijia; Irish Research Council
This paper proposes a novel and simple adaptive control algorithm for the effective delay control and resource utilization of end host multicast (EMcast) when the traffic load becomes heavy in a multigroup network with real-time flows constrained by (sigma, rho) regulators. The control algorithm is implemented at the overlay networks and provides more regulations through a novel (sigma, rho, lambda) regulator at each group end host who suffers from heavy input traffic. To our knowledge, it is the first work to incorporate traffic regulators into the end host multicast to control heavy traffic output. Our further contributions include a theoretical analysis and a set of results. We prove the existence and calculate the value of the rate threshold rho* such that for a given set of K groups, when the average rate of traffic entering the group end hosts rho macr > rho*, the ratio of the worst-case multicast delay bound of the proposed (sigma, rho, lambda) regulator over the traditional (sigma, rho) regulator is O(1/Kn) for any integer n. We also prove the efficiency of the novel algorithm and regulator in decreasing worst-case delays by conducting computer simulations.
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.
Efficient building management with IP-based wireless sensor network
(2009) Špinar, Rostislav; Muthukumaran, Panneer; De Paz Alberola, Rodolfo; Pesch, Dirk; Song, Weiping; Chaudhry, Shafique Ahmad; Sreenan, Cormac J.; Jafer, Essa; O'Flynn, Brendan; O'Donnell, James; Costa, Andrea; Keane, Marcus M.; Science Foundation Ireland
Existing Building/Energy Management Systems (BMS/EMS) fail to convey holistic performance to the building manager. A 20% reduction in energy consumption can be achieved by efficiently operated buildings compared with current practice. However, in the majority of buildings, occupant comfort and energy consumption analysis is primarily restricted by available sensor and meter data. Installation of a continuous monitoring process can significantly improve the building systems’ performance. We present WSN-BMDS, an IP-based wireless sensor network building monitoring and diagnostic system. The main focus of WSN-BMDS is to obtain much higher degree of information about the building operation then current BMSs are able to provide. Our system integrates a heterogeneous set of wireless sensor nodes with IEEE 802.11 backbone routers and the Global Sensor Network (GSN) web server. Sensing data is stored in a database at the back office via UDP protocol and can be access over the Internet using GSN. Through this demonstration, we show that WSN-BMDS provides accurate measurements of air-temperature, air-humidity, light, and energy consumption for particular rooms in our target building. Our interactive graphical user interface provides a user-friendly environment showing live network topology, monitor network statistics, and run-time management actions on the network. We also demonstrate actuation by changing the artificial light level in one of the rooms.
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.
Engineering an Open Web Syndication Interchange with Discovery and Recommender Capabilities
(Texas Digital Library, 2011) O'Riordan, Adrian P.; O'Mahoney, Oliver
Web syndication has become a popular means of delivering relevant information to people online but the complexity of standards, algorithms and applications pose considerable challenges to engineers. This paper describes the design and development of a novel Web-based syndication intermediary called InterSynd and a simple Web client as a proof of concept. We developed format-neutral middleware that sits between content sources and the user. Additional objectives were to add feed discovery and recommendation components to the intermediary. A search-based feed discovery module helps users find relevant feed sources. Implicit collaborative recommendations of new feeds are also made to the user. The syndication software built uses open standard XML technologies and the free open source libraries. Extensibility and re-configurability were explicit goals. The experience shows that a modular architecture can combine open source modules to build state-of-the-art syndication middleware and applications. The data produced by software metrics indicate the high degree of modularity retained.
An emergency-adaptive routing scheme for wireless sensor networks for building fire hazard monitoring
(MDPI, 2011-03-04) Zeng, Yuanyuan; Sreenan, Cormac J.; Sitanayah, Lanny; Xiong, Naixue; Park, Jong Hyuk; Zheng, Guilin; Higher Education Authority; Chinese Postdoctoral Science Foundation
Fire hazard monitoring and evacuation for building environments is a novel application area for the deployment of wireless sensor networks. In this context, adaptive routing is essential in order to ensure safe and timely data delivery in building evacuation and fire fighting resource applications. Existing routing mechanisms for wireless sensor networks are not well suited for building fires, especially as they do not consider critical and dynamic network scenarios. In this paper, an emergency-adaptive, real-time and robust routing protocol is presented for emergency situations such as building fire hazard applications. The protocol adapts to handle dynamic emergency scenarios and works well with the routing hole problem. Theoretical analysis and simulation results indicate that our protocol provides a real-time routing mechanism that is well suited for dynamic emergency scenarios in building fires when compared with other related work.
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.
Resource-aware video multicasting via access gateways in wireless mesh networks
(IEEE, 2012-04-19) Tu, Wanqing; Sreenan, Cormac J.; Chou, Chun Tung; Misra, Archan; Jha, Sanjay K.; Irish Research Council; Australian Research Council
This paper studies video multicasting in large-scale areas using wireless mesh networks. The focus is on the use of Internet access gateways that allow a choice of alternative routes to avoid potentially lengthy and low-capacity multihop wireless paths. A set of heuristic-based algorithms is described that together aim to maximize reliable network capacity: the two-tier integrated architecture algorithm, the weighted gateway uploading algorithm, the link-controlled routing tree algorithm, and the dynamic group management algorithm. These algorithms use different approaches to arrange nodes involved in video multicasting into a clustered and two-tier integrated architecture in which network protocols can make use of multiple gateways to improve system throughput. Simulation results are presented, showing that our multicasting algorithms can achieve up to 40 percent more throughput than other related published approaches.
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.
Location-aware mobile services for a smart city: Design, implementation and deployment
(Universidad de Talca – Chile, 2012-12) Calderoni, Luca; Maio, Dario; Palmieri, Paolo; Université Catholique de Louvain; Università di Bologna
A smart city is a high-performance urban context, where citizens are more aware of, and more integrated into the city life, thanks to an intelligent city information system. In this paper we design, implement and deploy a smart application that retrieves and conveys to the user relevant information on the user's surroundings. This case study application let us discuss the challenges involved in creating a location-aware mobile service based on live information coming from the city IT infrastructure. The service, that is currently being deployed in the Italian city of Cesena, has been designed with the goal of being a general model for future applications. In particular, we discuss location-aware and mobile development, cloud and cluster based geographical data storage, and spatial data computation. For each of these topics we provide implementation and deployment solutions based on currently available technology. In particular we propose an architecture based on a complex On-Line Transaction Processing (OLTP) infrastructure. Furthermore, this paper represents the first comprehensive, scientific study on the subject.

Browse

Browsing Computer Science - Journal Articles by Issue Date

Results Per Page

Sort Options