The Complexity of Approximately Solving Influence Diagrams

Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the treewidth and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.

Blind Characterisation of Sensors with Second-Order Dynamic Response

Compensation for the dynamic response of a temperature sensor usually involves the estimation of its input on the basis of the measured output and model parameters. In the case of temperature measurement, the sensor dynamic response is strongly dependent on the measurement environment and fluid velocity. Estimation of time-varying sensor model parameters therefore requires continuous textit{in situ} identification. This can be achieved by employing two sensors with different dynamic properties, and exploiting structural redundancy to deduce the sensor models from the resulting data streams. Most existing approaches to this problem assume first-order sensor dynamics. In practice, however second-order models are more reflective of the dynamics of real temperature sensors, particularly when they are encased in a protective sheath. As such, this paper presents a novel difference equation approach to solving the blind identification problem for sensors with second-order models. The approach is based on estimating an auxiliary ARX model whose parameters are related to the desired sensor model parameters through a set of coupled non-linear algebraic equations. The ARX model can be estimated using conventional system identification techniques and the non-linear equations can be solved analytically to yield estimates of the sensor models. Simulation results are presented to demonstrate the efficiency of the proposed approach under various input and parameter conditions.

An approach to determine the local boundary of small disturbance voltage stability region in a cut-set power space:基于微扰的割集电压稳定域局部边界求解方法

A new approach to determine the local boundary of voltage stability region in a cut-set power space (CVSR) is presented. Power flow tracing is first used to determine the generator-load pair most sensitive to each branch in the interface. The generator-load pairs are then used to realize accurate small disturbances by controlling the branch power flow in increasing and decreasing directions to obtain new equilibrium points around the initial equilibrium point. And, continuous power flow is used starting from such new points to get the corresponding critical points around the initial critical point on the CVSR boundary. Then a hyperplane cross the initial critical point can be calculated by solving a set of linear algebraic equations. Finally, the presented method is validated by some systems, including New England 39-bus system, IEEE 118-bus system, and EPRI-1000 bus system. It can be revealed that the method is computationally more efficient and has less approximation error. It provides a useful approach for power system online voltage stability monitoring and assessment. This work is supported by National Natural Science Foundation of China (No. 50707019), Special Fund of the National Basic Research Program of China (No. 2009CB219701), Foundation for the Author of National Excellent Doctoral Dissertation of PR China (No. 200439), Tianjin Municipal Science and Technology Development Program (No. 09JCZDJC25000), National Major Project of Scientific and Technical Supporting Programs of China During the 11th Five-year Plan Period (No. 2006BAJ03A06). ©2009 State Grid Electric Power Research Institute Press.

"Should I prioritize medical problem solving or attentive listening?": the dilemmas and challenges that medical students experience when learning to conduct consultations

Objective: Communication skills can be trained alongside clinical reasoning, history taking or clinical examination skills. This is advocated as a solution to the low transfer of communication skills. Still, students have to integrate the knowledge/skills acquired during different curriculum parts in patient consultations at some point. How do medical students experience these integrated consultations within a simulated environment and in real practice when dealing with responsibility?

Methods: Six focus groups were conducted with (pre-)/clerkship students.

Results: Students were motivated to practice integrated consultations with simulated patients and felt like 'real physicians'. However, their focus on medical problem solving drew attention away from improving their communication skills. Responsibility for real patients triggered students' identity development. This identity formation guided the development of an own consultation style, a process that was hampered by conflicting demands of role models.

Conclusion: Practicing complete consultations results in the dilemma of prioritizing medical problem solving above attention for patient communication. Integrated consultation training advances this dilemma to the pre-clerkship period. During clerkships this dilemma is heightened because real patients trigger empathy and responsibility, which invites students to define their role as doctor.

Practice Implications: When training integrated consultations, educators should pay attention to students' learning priorities and support the development of students' professional identity.

Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs

The ability of an agent to make quick, rational decisions in an uncertain environment is paramount for its applicability in realistic settings. Markov Decision Processes (MDP) provide such a framework, but can only model uncertainty that can be expressed as probabilities. Possibilistic counterparts of MDPs allow to model imprecise beliefs, yet they cannot accurately represent probabilistic sources of uncertainty and they lack the efficient online solvers found in the probabilistic MDP community. In this paper we advance the state of the art in three important ways. Firstly, we propose the first online planner for possibilistic MDP by adapting the Monte-Carlo Tree Search (MCTS) algorithm. A key component is the development of efficient search structures to sample possibility distributions based on the DPY transformation as introduced by Dubois, Prade, and Yager. Secondly, we introduce a hybrid MDP model that allows us to express both possibilistic and probabilistic uncertainty, where the hybrid model is a proper extension of both probabilistic and possibilistic MDPs. Thirdly, we demonstrate that MCTS algorithms can readily be applied to solve such hybrid models.

Exact and heuristic methods for solving Boolean games

Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents’ goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computation of solution concepts. Although some suggestions for solving specific classes of Boolean games have been made in the literature, there is currently no work available on the practical performance. In this paper, we propose the first technique to solve general Boolean games that does not require an exponential translation to normal-form games. Our method is based on disjunctive answer set programming and computes solutions (equilibria) of arbitrary Boolean games. It can be applied to a wide variety of solution concepts, and can naturally deal with extensions of Boolean games such as constraints and costs. We present detailed experimental results in which we compare the proposed method against a number of existing methods for solving specific classes of Boolean games, as well as adaptations of methods that were initially designed for normal-form games. We found that the heuristic methods that do not require all payoff matrix entries performed well for smaller Boolean games, while our ASP based technique is faster when the problem instances have a higher number of agents or action variables.

Using Answer Set Programming for Solving Boolean Games

Boolean games are a framework for reasoning about the rational behaviour of agents, whose goals are formalized using propositional formulas. They offer an attractive alternative to normal-form games, because they allow for a more intuitive and more compact encoding. Unfortunately, however, there is currently no general, tailor-made method available to compute the equilibria of Boolean games. In this paper, we introduce a method for finding the pure Nash equilibria based on disjunctive answer set programming. Our method is furthermore capable of finding the core elements and the Pareto optimal equilibria, and can easily be modified to support other forms of optimality, thanks to the declarative nature of disjunctive answer set programming. Experimental results clearly demonstrate the effectiveness of the proposed method.

The effect of preferential paw usage on dogs' (Canis familiaris) performance in a manipulative problem-solving task

In a number of species, individuals showing lateralized hand/paw usage (i.e. the preferential use of either the right or left paw) compared to ambilateral individuals have been shown to be more proactive in novel situations. In the current study we used an established test to assess preferential paw usage in dogs (the Kong test) and then compared the performance of ambilateral and lateralized dogs as well as left- vs. right-pawed dogs in a novel manipulative problem solving task. Results showed an equal proportion of ambilateral and lateralized dogs but contrary to predictions non-lateralized dogs were faster at accessing the apparatus in test trials. No differences emerged between right- and left-pawed dogs. Results are discussed in relation to previous studies on lateralization. © 2013 Elsevier B.V.

A Hybrid Imperialist Approach in Solving University Timetabling Problems. Information Sciences. Vol. 283, 1-21

Generating timetables for an institution is a challenging and time consuming task due to different demands on the overall structure of the timetable. In this paper, a new hybrid method which is a combination of a great deluge and artificial bee colony algorithm (INMGD-ABC) is proposed to address the university timetabling problem. Artificial bee colony algorithm (ABC) is a population based method that has been introduced in recent years and has proven successful in solving various optimization problems effectively. However, as with many search based approaches, there exist weaknesses in the exploration and exploitation abilities which tend to induce slow convergence of the overall search process. Therefore, hybridization is proposed to compensate for the identified weaknesses of the ABC. Also, inspired from imperialist competitive algorithms, an assimilation policy is implemented in order to improve the global exploration ability of the ABC algorithm. In addition, Nelder–Mead simplex search method is incorporated within the great deluge algorithm (NMGD) with the aim of enhancing the exploitation ability of the hybrid method in fine-tuning the problem search region. The proposed method is tested on two differing benchmark datasets i.e. examination and course timetabling datasets. A statistical analysis t-test has been conducted and shows the performance of the proposed approach as significantly better than basic ABC algorithm. Finally, the experimental results are compared against state-of-the art methods in the literature, with results obtained that are competitive and in certain cases achieving some of the current best results to those in the literature.

Nonequilibrium processes from generalized Langevin equations: Realistic nanoscale systems connected to two thermal baths

We extend the generalized Langevin equation (GLE) method [L. Stella, C. D. Lorenz, and L. Kantorovich, Phys. Rev. B 89, 134303 (2014)] to model a central classical region connected to two realistic thermal baths at two different temperatures. In such nonequilibrium conditions a heat flow is established, via the central system, in between the two baths. The GLE-2B (GLE two baths) scheme permits us to have a realistic description of both the dissipative central system and its surrounding baths. Following the original GLE approach, the extended Langevin dynamics scheme is modified to take into account two sets of auxiliary degrees of freedom corresponding to the mapping of the vibrational properties of each bath. These auxiliary variables are then used to solve the non-Markovian dissipative dynamics of the central region. The resulting algorithm is used to study a model of a short Al nanowire connected to two baths. The results of the simulations using the GLE-2B approach are compared to the results of other simulations that were carried out using standard thermostatting approaches (based on Markovian Langevin and Nosé-Hoover thermostats). We concentrate on the steady-state regime and study the establishment of a local temperature profile within the system. The conditions for obtaining a flat profile or a temperature gradient are examined in detail, in agreement with earlier studies. The results show that the GLE-2B approach is able to treat, within a single scheme, two widely different thermal transport regimes, i.e., ballistic systems, with no temperature gradient, and diffusive systems with a temperature gradient.