Physical Sciences and Mathematics Commons^™

Drift Detection Using Uncertainty Distribution Divergence, Patrick Lindstrom, Brian Mac Namee, Sarah Jane Delany

Conference papers

Concept drift is believed to be prevalent inmost data gathered from naturally occurring processes andthus warrants research by the machine learning community.There are a myriad of approaches to concept drift handlingwhich have been shown to handle concept drift with varyingdegrees of success.

However, most approaches make the keyassumption that the labelled data will be available at nolabelling cost shortly after classification, an assumption whichis often violated. The high labelling cost in many domainsprovides a strong motivation to reduce the number of labelledinstances required to handle concept drift. Explicit detectionapproaches that do not require labelled instances to detectconcept drift show great …

Mobile Phone Graph Evolution: Findings, Model And Interpretation, Siyuan Liu, Lei Li, Christos Faloutsos, Lionel M. Ni

LARC Research Publications

What are the features of mobile phone graph along the time? How to model these features? What are the interpretation for the evolutional graph generation process? To answer the above challenging problems, we analyze a massive who-call-whom networks as long as a year, gathered from records of two large mobile phone communication networks both with 2 million users and 2 billion of calls. We examine the calling behavior distribution at multiple time scales (e.g. day, week, month and quarter), and find that the distribution is not only skewed with a heavy tail, but also changing at different time scales. How …

Towards Textually Describing Complex Video Contents With Audio-Visual Concept Classifiers, Chun Chet Tan, Yu-Gang Jiang, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

Automatically generating compact textual descriptions of complex video contents has wide applications. With the recent advancements in automatic audio-visual content recognition, in this paper we explore the technical feasibility of the challenging issue of precisely recounting video contents. Based on cutting-edge automatic recognition techniques, we start from classifying a variety of visual and audio concepts in video contents. According to the classification results, we apply simple rule-based methods to generate textual descriptions of video contents. Results are evaluated by conducting carefully designed user studies. We find that the state-of-the-art visual and audio concept classification, although far from perfect, is able …

Capir: Collaborative Action Planning With Intention Recognition, Nguyen T., Hsu D., Lee W., Tze-Yun Leong, Kaelbling L., Lozano-Perez T., Grant A.

Research Collection School Of Computing and Information Systems

We apply decision theoretic techniques to construct nonplayer characters that are able to assist a human player in collaborative games. The method is based on solving Markov decision processes, which can be difficult when the game state is described by many variables. To scale to more complex games, the method allows decomposition of a game task into subtasks, each of which can be modelled by a Markov decision process. Intention recognition is used to infer the subtask that the human is currently performing, allowing the helper to assist the human in performing the correct task. Experiments show that the method …

A Pomdp Model For Guiding Taxi Cruising In A Congested Urban City, Lucas Agussurja, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We consider a partially observable Markov decision process (POMDP) model for improving a taxi agent cruising decision in a congested urban city. Using real-world data provided by a large taxi company in Singapore as a guide, we derive the state transition function of the POMDP. Specifically, we model the cruising behavior of the drivers as continuous-time Markov chains. We then apply dynamic programming algorithm for finding the optimal policy of the driver agent. Using a simulation, we show that this policy is significantly better than a greedy policy in congested road network.

A Brain-Inspired Model Of Hierarchical Planner, Budhitama Subagdja, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

Hierarchical planning is an approach of planning by composing and executing hierarchically arranged plans to solve some problems. Most symbolic-based hierarchical planners have been devised to allow the knowledge to be described expressively. However, a great challenge is to automatically seek and acquire new plans on the fly. This paper presents a novel neural-based model of hierarchical planning that can seek and acquired new plans on-line if the necessary knowledge are lacking. Inspired by findings in neuropsychology, plans can be inherently learnt, retrieved, and manipulated simultaneously rather than discretely processed like in most symbolic approaches. Using a multi-channel adaptive resonance …

Dynamic Behavior Sequencing For Hybrid Robot Architectures, Gilbert L. Peterson, Jeffrey P. Duffy, Daylond J. Hooper

Faculty Publications

Hybrid robot control architectures separate planning, coordination, and sensing and acting into separate processing layers to provide autonomous robots both deliberative and reactive functionality. This approach results in systems that perform well in goal-oriented and dynamic environments. Often, the interfaces and intents of each functional layer are tightly coupled and hand coded so any system change requires several changes in the other layers. This work presents the dynamic behavior hierarchy generation (DBHG) algorithm, which uses an abstract behavior representation to automatically build a behavior hierarchy for meeting a task goal. The generation of the behavior hierarchy occurs without knowledge of …

Influence Diagrams With Memory States: Representation And Algorithms, Xiaojian Wu, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Influence diagrams (IDs) offer a powerful framework for decision making under uncertainty, but their applicability has been hindered by the exponential growth of runtime and memory usage--largely due to the no-forgetting assumption. We present a novel way to maintain a limited amount of memory to inform each decision and still obtain near-optimal policies. The approach is based on augmenting the graphical model with memory states that represent key aspects of previous observations--a method that has proved useful in POMDP solvers. We also derive an efficient EM-based message-passing algorithm to compute the policy. Experimental results show that this approach produces highquality …

Allocating Resources In Multiagent Flowshops With Adaptive Auctions, Hoong Chuin Lau, Zhengyi Zhao, Sam Shuzhi Ge, Thong Heng Lee

Research Collection School Of Computing and Information Systems

In this paper, we consider the problem of allocating machine resources among multiple agents, each of which is responsible to solve a flowshop scheduling problem. We present an iterated combinatorial auction mechanism in which bid generation is performed within each agent, while a price adjustment procedure is performed by a centralized auctioneer. While this approach is fairly well-studied in the literature, our primary innovation is in an adaptive price adjustment procedure, utilizing variable step-size inspired by adaptive PID-control theory coupled with utility pricing inspired by classical microeconomics. We compare with the conventional price adjustment scheme proposed in Fisher (1985), and …

Improving Occupancy Grid Fastslam By Integrating Navigation Sensors, Christopher Weyers, Gilbert L. Peterson

Faculty Publications

When an autonomous vehicle operates in an unknown environment, it must remember the locations of environmental objects and use those object to maintain an accurate location of itself. This vehicle is faced with Simultaneous Localization and Mapping (SLAM), a circularly defined robotics problem of map building with no prior knowledge. The SLAM problem is a difficult but critical component of autonomous vehicle exploration with applications to search and rescue missions. This paper presents the first SLAM solution combining stereo cameras, inertial measurements, and vehicle odometry into a Multiple Integrated Navigation Sensor (MINS) path. The FastSLAM algorithm, modified to make use …

Taxisim: A Multiagent Simulation Platform For Evaluating Taxi Fleet Operations, Shih-Fen Cheng, Thi Duong Nguyen

Research Collection School Of Computing and Information Systems

Taxi service is an important mode of public transportation in most metropolitan areas since it provides door-to-door convenience in the public domain. Unfortunately, despite all the convenience taxis bring, taxi fleets are also extremely inefficient to the point that over 50% of its operation time could be spent in idling state. Improving taxi fleet operation is an extremely challenging problem, not just because of its scale, but also due to fact that taxi drivers are self-interested agents that cannot be controlled centrally. To facilitate the study of such complex and decentralized system, we propose to construct a multiagent simulation platform …

Finding Robust-Under-Risk Solutions For Flowshop Scheduling, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We propose and explore, in the context of benchmark problems for flowshop scheduling, a risk-based concept of robustness for optimization problems. This risk-based concept is in distinction to, and complements, the uncertainty-based concept employed in the field known as robust optimization. Implementation of our concept requires problem solution methods that sample the solution space intelligently and that produce large numbers of distinct sample points. With these solutions to hand, their robustness scores are easily obtained and heuristically robust solutions found. We find evolutionary computation to be effective for this purpose on these problems.

Real-World Parameter Tuning Using Factorial Design With Parameter Decomposition, Aldy Gunawan, Hoong Chuin Lau, Elaine Wong

Research Collection School Of Computing and Information Systems

In this paper, we explore the idea of improving the efficiency of factorial design for parameter tuning of metaheuristics. In a standard full factorial design, the number of runs increases exponentially as the number of parameters. To reduce the parameter search space, one option is to first partition parameters into disjoint categories. While this may be done manually based on user guidance, an automated approach proposed in this paper is to apply a fractional factorial design to partition parameters based on their main effects where each partition is then tuned independently. With a careful choice of fractional design, our approach …

Message-Passing Algorithms For Quadratic Programming Formulations Of Map Estimation, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Computing maximum a posteriori (MAP) estimation in graphical models is an important inference problem with many applications. We present message-passing algorithms for quadratic programming (QP) formulations of MAP estimation for pairwise Markov random fields. In particular, we use the concave-convex procedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP formulation. A similar technique is used to derive a globally convergent algorithm for the convex QP relaxation of MAP. We also show that a recently developed expectation-maximization (EM) algorithm for the QP formulation of MAP can be derived from the CCCP perspective. Experiments on synthetic and real-world problems …

Scalable Multiagent Planning Using Probabilistic Inference, Akshat Kumar, Shlomo Zilberstein, Marc Toussaint

Research Collection School Of Computing and Information Systems

Multiagent planning has seen much progress with the development of formal models such as Dec-POMDPs. However, the complexity of these models -- NEXP-Complete even for two agents -- has limited scalability. We identify certain mild conditions that are sufficient to make multiagent planning amenable to a scalable approximation w.r.t. the number of agents. This is achieved by constructing a graphical model in which likelihood maximization is equivalent to plan optimization. Using the Expectation-Maximization framework for likelihood maximization, we show that the necessary inference can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We …

Solution Pluralism And Metaheuristics, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau, Frederic H. Murphy, David Harlan Wood

Research Collection School Of Computing and Information Systems

Solution pluralism is an approach to problem solving and deliberation. It employs a plurality of distinct solutions for a decision problem for aiding decision making. The concept is well established in existing practice, although perhaps not recognized as such. This paper: (1) presents the concept as a generalization of established practice, (2) briefly describes successful uses of the concept in practice, and (3) presents several areas that appear would benefit from application of the concept. Throughout, the role of metaheuristics in finding the pluralities of solutions is emphasized.

A Novel Methodology For Evaluating User Interfaces In Health Care, Luca Longo, Bridget Kane

Conference papers

A pilot study is reported to identify an improved method of evaluating digital user interfaces in health care. Experience and developments from the aviation industry and the NASA-TLX mental workload assessment tools are applied in conjunction with Nielsen heuristics for evaluating an Electronic Health Record System in an Irish hospital. The NASA-TLX performs subjective workload assessments on operators working with various human-computer systems. Results suggest that depending on the cognitive workload and the working context of users, the usability will differ for the same digital interface. We conclude that incorporating the NASA-TLX with Nielsen's heuristics offers a more reliable method …

Intelligent Systems Development In A Non Engineering Curriculum, Emily A. Brand, William L. Honig, Matthew Wojtowicz

Computer Science: Faculty Publications and Other Works

Much of computer system development today is programming in the large - systems of millions of lines of code distributed across servers and the web. At the same time, microcontrollers have also become pervasive in everyday products, economical to manufacture, and represent a different level of learning about system development. Real world systems at this level require integrated development of custom hardware and software.

How can academic institutions give students a view of this other extreme - programming on small microcontrollers with specialized hardware? Full scale system development including custom hardware and software is expensive, beyond the range of any …

Effects Of Appearance And Functions On Likability And Perceived Occupational Suitability Of Robots, Sau-Lai Lee, Ivy Yee-Man Lau, Ying-Yi Hong

Research Collection School of Social Sciences

This article reports three experiments that examined the association between (a) appearances and perceived capabilities of robots, (b) appearance and capabilities of robots and liking for the robots, and (c) perceived capabilities of robots and judgments concerning their suitability for different occupations. In Experiment 1, the authors found that participants perceived human- and animal-like robots to have relatively more warmth-related (e.g., emotion) capabilities than machinelike robots have. In Experiment 2, the authors found that liking for robots was not affected by their human likeness or their having warmth or competence capabilities. In Experiment 3, participants generally thought that robots should …

Multiagent Coalition Formation In Uncertain Environments With Type-Changing Influences And Its Application Towards Forming Human Coalitions, Nobel A. Khandaker

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

We aim to solve the problem forming multiagent coalitions in uncertain environments where the coalition members’ capability of solving tasks change due to their learning. The MCFP-Mproblem for the agents refers to forming or joining coalitions on behalf of a set of human users so that those human users can solve tasks and improve their types (expertise) to improve their performances over time. MCFP-A problem for a set of agents refers to their forming or joining coalitions so that they are able to solve a set of assigned tasks while optimize their performance over time. We propose the Integrated Human …

Message-Passing Algorithms For Large Structured Decentralized Pomdps, Akshat Kumar, Shlomo Zilberstein

Research Collection School Of Computing and Information Systems

Decentralized POMDPs provide a rigorous framework for multi-agent decision-theoretic planning. However, their high complexity has limited scalability. In this work, we present a promising new class of algorithms based on probabilistic inference for infinite-horizon ND-POMDPs---a restricted Dec-POMDP model. We first transform the policy optimization problem to that of likelihood maximization in a mixture of dynamic Bayes nets (DBNs). We then develop the Expectation-Maximization (EM) algorithm for maximizing the likelihood in this representation. The EM algorithm for ND-POMDPs lends itself naturally to a simple message-passing paradigm guided by the agent interaction graph. It is thus highly scalable w.r.t. the number of …

Distributed Model Shaping For Scaling To Decentralized Pomdps With Hundreds Of Agents, Prasanna Velagapudi, Pradeep Reddy Varakantham, Katia Sycara, Paul Scerri

Research Collection School Of Computing and Information Systems

The use of distributed POMDPs for cooperative teams has been severely limited by the incredibly large joint policy- space that results from combining the policy-spaces of the individual agents. However, much of the computational cost of exploring the entire joint policy space can be avoided by observing that in many domains important interactions between agents occur in a relatively small set of scenarios, previously defined as coordination locales (CLs) [11]. Moreover, even when numerous interactions might occur, given a set of individual policies there are relatively few actual interactions. Exploiting this observation and building on an existing model shaping algorithm, …

Incremental Dcop Search Algorithms For Solving Dynamic Dcop Problems, William Yeoh, Pradeep Varakantham, Xiaoxun Sun, Sven Koenig

Research Collection School Of Computing and Information Systems

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper …

Decentralized Decision Support For An Agent Population In Dynamic And Uncertain Domains, Pradeep Reddy Varakantham, Shih-Fen Cheng, Thi Duong Nguyen

Research Collection School Of Computing and Information Systems

This research is motivated by problems in urban transportation and labor mobility, where the agent flow is dynamic, non-deterministic and on a large scale. In such domains, even though the individual agents do not have an identity of their own and do not explicitly impact other agents, they have implicit interactions with other agents. While there has been much research in handling such implicit effects, it has primarily assumed controlled movements of agents in static environments. We address the issue of decision support for individual agents having involuntary movements in dynamic environments . For instance, in a taxi fleet serving …

Adaptive Decision Support For Structured Organizations: A Case For Orgpomdps, Pradeep Reddy Varakantham, Nathan Schurr, Alan Carlin, Christopher Amato

Research Collection School Of Computing and Information Systems

In today's world, organizations are faced with increasingly large and complex problems that require decision-making under uncertainty. Current methods for optimizing such decisions fall short of handling the problem scale and time constraints. We argue that this is due to existing methods not exploiting the inherent structure of the organizations which solve these problems. We propose a new model called the OrgPOMDP (Organizational POMDP), which is based on the partially observable Markov decision process (POMDP). This new model combines two powerful representations for modeling large scale problems: hierarchical modeling and factored representations. In this paper we make three key contributions: …

A Simple Curious Agent To Help People Be Curious, Han Yu, Zhiqi Shen, Chunyan Miao, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

Curiosity is an innately rewarding state of mind that, over the millennia, has driven the human race to explore and discover. Many researches in pedagogical science have confirmed the importance of being curious to the students' cognitive development. However, in the newly popular virtual world-based learning environments (VLEs), there is currently a lack of attention being paid to enhancing the learning experience by stimulating the learners' curiosity. In this paper, we propose a simple model for curious agents (CAs) which can be used to stimulate learners' curiosity in VLEs. Potential future research directions will be discussed.

Recognition Situations Using Extended Dempster-Shafer Theory, Susan Mckeever

Other resources

Weiser’s [111] vision of pervasive computing describes a world where technology seamlessly integrates into the environment, automatically responding to peoples’ needs. Underpinning this vision is the ability of systems to automatically track the situation of a person. The task of situation recognition is critical and complex: noisy and unreliable sensor data, dynamic situations, unpredictable human behaviour and changes in the environment all contribute to the complexity. No single recognition technique is suitable in all environments. Factors such as availability of training data, ability to deal with uncertain information and transparency to the user will determine which technique to use in …

Punctuated Anytime Learning And The Xpilot-Ai Combat Environment, Phillip Fritzsche

Computer Science Honors Papers

In this paper, research is presented on an application of Punctuated Anytime Learning with Fitness Biasing, a type of computational intelligence and evolutionary learning, for real-­time learning of autonomous agents controllers in the space combat game Xpilot. Punctuated Anytime Learning was originally developed as a means of effective learning in the field of evolutionary robotics. An analysis was performed on the game environment to determine optimal environmental settings for use during learning, and Fitness Biasing is employed using this information to learn intelligent behavior for a video game agent controller in real-­time. Xpilot-­AI, an Xpilot add-­on designed for testing learning …

Corrective Gradient Refinement For Mobile Robot Localization, Joydeep Biswas, Manuela M. Veloso, Brian Coltin

Computer Science Department Faculty Publication Series

Particle filters for mobile robot localization must balance computational requirements and accuracy of localization. Increasing the number of particles in a particle filter improves accuracy, but also increases the computational requirements. Hence, we investigate a different paradigm to better utilize particles than to increase their numbers. To this end, we introduce the Corrective Gradient Refinement (CGR) algorithm that uses the state space gradients of the observation model to improve accuracy while maintaining low computational requirements. We develop an observation model for mobile robot localization using point cloud sensors (LIDAR and depth cameras) with vector maps. This observation model is then …

Improving Service Through Just-In-Time Concept In A Dynamic Operational Environment, Kar Way Tan, Hoong Chuin Lau, Na Fu

Research Collection School Of Computing and Information Systems

This paper is concerned with the problem of Just-In-Time (JIT) job scheduling in a dynamic environment under uncertainty to attain timely service. We provide an approach, based on robust scheduling concepts, to analytically evaluate the expected cost of earliness and tardiness for each job and also the project. In addition, we search for a schedule execution policy with the minimum robust cost such that for a given risk level (epsilon), the actual realized schedule has (1 - epsilon) probability of completing with less than or equal to this robust cost. Our method is quite generic, and can be applied to …