Engineering Commons^™

A Mechanism For Organizing Last-Mile Service Using Non-Dedicated Fleet, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Unprecedented pace of urbanization and rising income levels have fueled the growth of car ownership in almost all newly formed megacities. Such growth has congested the limited road space and significantly affected the quality of life in these megacities. Convincing residents to give up their cars and use public transport is the most effective way in reducing congestion; however, even with sufficient public transport capacity, the lack of last-mile (from the transport hub to the destination) travel services is the major deterrent for the adoption of public transport. Due to the dynamic nature of such travel demands, fixed-size fleets will …

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Varakantham, William Yeoh, Hoong Chuin Lau, Shih-Fen Cheng

Research Collection School Of Computing and Information Systems

Multi-agent planning is a well-studied problem with various applications including disaster rescue, urban transportation and logistics, both for autonomous agents and for decision support to humans. Due to computational constraints, existing research typically focuses on one of two scenarios: unstructured domains with many agents where we are content with heuristic solutions, or domains with small numbers of agents or special structure where we can provide provably near-optimal solutions. By contrast, in this paper, we focus on providing provably near-optimal solutions for domains with large numbers of agents, by exploiting a common domain-general property: if individual agents each have limited influence …

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoffrey J. Gordon, Pradeep Varakantham, William Yeoh, Hoong Chuin Lau, Ajay S. Aravamudhan, Shih-Fen Cheng

Research Collection School Of Computing and Information Systems

Multi-agent planning is a well-studied problem with various applications including disaster rescue, urban transportation and logistics, both for autonomous agents and for decision support to humans. Due to computational constraints, existing research typically focuses on one of two scenarios: unstructured domains with many agents where we are content with heuristic solutions, or domains with small numbers of agents or special structure where we can provide provably near-optimal solutions. By contrast, in this paper, we focus on providing provably near-optimal solutions for domains with large numbers of agents, by exploiting a common domain-general property: if individual agents each have limited influence …

Knowledge-Driven Autonomous Commodity Trading Advisor, Yee Pin Lim, Shih-Fen Cheng

Research Collection School Of Computing and Information Systems

The myth that financial trading is an art has been mostly destroyed in the recent decade due to the proliferation of algorithmic trading. In equity markets, algorithmic trading has already bypass human traders in terms of traded volume. This trend seems to be irreversible, and other asset classes are also quickly becoming dominated by the machine traders. However, for asset that requires deeper understanding of physicality, like the trading of commodities, human traders still have significant edge over machines. The primary advantage of human traders in such market is the qualitative expert knowledge that requires traders to consider not just …

Cognitive Architectures And Autonomy: Commentary And Response, Włodzisław Duch, Ah-Hwee Tan, Stan Franklin

Research Collection School Of Computing and Information Systems

This paper provides a very useful and promising analysis and comparison of current architectures of autonomous intelligent systems acting in real time and specific contexts, with all their constraints. The chosen issue of Cognitive Architectures and Autonomy is really a challenge for AI current projects and future research. I appreciate and endorse not only that challenge but many specific choices and claims; in particular: (i) that “autonomy” is a key concept for general intelligent systems; (ii) that “a core issue in cognitive architecture is the integration of cognitive processes ....”; (iii) the analysis of features and capabilities missing in current …

Preoperative Planning Of Robotics-Assisted Minimally Invasive Cardiac Surgery Under Uncertainty, Hamidreza Azimian

Electronic Thesis and Dissertation Repository

In this thesis, a computational framework for patient-specific preoperative planning of Robotics-Assisted Minimally Invasive Cardiac Surgery (RAMICS) is developed. It is expected that preoperative planning of RAMICS will improve the rate of success by considering robot kinematics, patient-specific thoracic anatomy, and procedure-specific intraoperative conditions. Given the significant anatomical features localized in the preoperative computed tomography images of a patient's thorax, port locations and robot orientations (with respect to the patient's body coordinate frame) are determined to optimize characteristics such as dexterity, reachability, tool approach angles and maneuverability. In this thesis, two approaches for preoperative planning of RAMICS are proposed that …

Bidder Behaviors In Repeated B2b Procurement Auctions, Jong Han Park, Jae Kyu Lee, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

B2B auctions play a key role in a firm's procurement process. Even though it is known that repetition is a key characteristic of procurement auctions, traditional auctioneers typically have not put in place a suitable mechanism that supports repetitive auctions effectively. In this paper, we empirically investigate what has taken place in repeated procurement auctions based on real world data from a major outsourcing company of MRO (Maintenance, Repair and Operations) items in Korea. From this empirical study, we discovered the followings. First, we discovered that the repeated bidders contribute majority of all bids, and that the number of new …

Real-Time Mobile Stereo Vision, Bryan Hale Bodkin

Masters Theses

Computer stereo vision is used extract depth information from two aligned cameras and there are a number of hardware and software solutions to solve the stereo correspondence problem. However few solutions are available for inexpensive mobile platforms where power and hardware are major limitations. This Thesis will proposes a method that competes with an existing OpenCV stereo correspondence method in speed and quality, and is able to run on generic multi core CPU’s.

Uncertain Congestion Games With Assorted Human Agent Populations, Asrar Ahmed, Pradeep Reddy Varakantham, Shih-Fen Cheng

Research Collection School Of Computing and Information Systems

Congestion games model a wide variety of real-world resource congestion problems, such as selfish network routing, traffic route guidance in congested areas, taxi fleet optimization and crowd movement in busy areas. However, existing research in congestion games assumes: (a) deterministic movement of agents between resources; and (b) perfect rationality (i.e. maximizing their own expected value) of all agents. Such assumptions are not reasonable in dynamic domains where decision support has to be provided to humans. For instance, in optimizing the performance of a taxi fleet serving a city, movement of taxis can be involuntary or nondeterministic (decided by the specific …

Dynamic Stochastic Orienteering Problems For Risk-Aware Applications, Hoong Chuin Lau, William Yeoh, Pradeep Varakantham, Duc Thien Nguyen

Research Collection School Of Computing and Information Systems

Orienteering problems (OPs) are a variant of the well-known prize-collecting traveling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations travel times between cities are assumed to be time independent and the route provided is independent of the risk preference (with respect to violating the deadline) of the user. To address these issues, we make the following contributions: We introduce (1) a dynamic …

Toward Large-Scale Agent Guidance In An Urban Taxi Service, Agussurja Lucas, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Empty taxi cruising represents a wastage of resources in the context of urban taxi services. In this work, we seek to minimize such wastage. An analysis of a large trace of taxi operations reveals that the services’ inefficiency is caused by drivers’ greedy cruising behavior. We model the existing system as a continuous time Markov chain. To address the problem, we propose that each taxi be equipped with an intelligent agent that will guide the driver when cruising for passengers. Then, drawing from AI literature on multiagent planning, we explore two possible ways to compute such guidance. The first formulation …

The Patrol Scheduling Problem, Hoong Chuin Lau, Aldy Gunawan

Research Collection School Of Computing and Information Systems

This paper presents the problem of scheduling security teams to patrol a mass rapid transit rail network of a large urban city. The main objective of patrol scheduling is to deploy security teams to stations at varying time periods of the network subject to rostering as well as security-related constraints. We present a mathematical programming model for this problem. We then discuss the aspect of injecting randomness by varying the start times, the break times for each team as well as the number of visits required for each station according to their reported vulnerability. Finally, we present results for the …

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Kyriakos MOURATIDIS

Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …

Analog Vlsi Implementation Of Support Vector Machine Learning And Classification, Sheng-Yu Peng, Bradley Minch, Paul Hasler

Bradley Minch

We propose an analog VLSI approach to implementing the projection neural networks adapted for the supportvector machine with radial-basis kernel functions, which are realized by a proposed floating-gate bump circuit with the adjustable width. Other proposed circuits include simple current mirrors and log-domain Alters. Neither resistors nor amplifiers are employed. Therefore it is suitable for large-scale neural network implementations. We show the measurement results of the bump circuit and verify the resulting analog signal processing system on the transistor level by using a SPICE simulator. The same approach can also be applied to the support vectorregression. With these analog signal …

Decision Support For Agent Populations In Uncertain And Congested Environments, Pradeep Reddy Varakantham, Shih-Fen Cheng, Geoff Gordon, Asrar Ahmed

Research Collection School Of Computing and Information Systems

This research is motivated by large scale problems in urban transportation and labor mobility where there is congestion for resources and uncertainty in movement. In such domains, even though the individual agents do not have an identity of their own and do not explicitly interact with other agents, they effect other agents. While there has been much research in handling such implicit effects, it has primarily assumed deterministic movements of agents. We address the issue of decision support for individual agents that are identical and have involuntary movements in dynamic environments. For instance, in a taxi fleet serving a city, …

Logistics Orchestration Modeling And Evaluation For Humanitarian Relief, Hoong Chuin Lau, Zhengping Li, Xin Du, Heng Jiang, Robert De Souza

Research Collection School Of Computing and Information Systems

This paper proposes an orchestration model for post-disaster response that is aimed at automating the coordination of scarce resources that minimizes the loss of human lives. In our setting, different teams are treated as agents and their activities are "orchestrated" to optimize rescue performance. Results from simulation are analysed to evaluate the performance of the optimization model.

Incorporating Memory And Learning Mechanisms Into Meta-Raps, Arif Arin

Engineering Management & Systems Engineering Theses & Dissertations

Due to the rapid increase of dimensions and complexity of real life problems, it has become more difficult to find optimal solutions using only exact mathematical methods. The need to find near-optimal solutions in an acceptable amount of time is a challenge when developing more sophisticated approaches. A proper answer to this challenge can be through the implementation of metaheuristic approaches. However, a more powerful answer might be reached by incorporating intelligence into metaheuristics.

Meta-RaPS (Metaheuristic for Randomized Priority Search) is a metaheuristic that creates high quality solutions for discrete optimization problems. It is proposed that incorporating memory and learning …

A Location-Aware Architecture Supporting Intelligent Real-Time Mobile Applications, Sean J. Barbeau

USF Tampa Graduate Theses and Dissertations

This dissertation presents LAISYC, a modular location-aware architecture for intelligent real-time mobile applications that is fully-implementable by third party mobile app developers and supports high-precision and high-accuracy positioning systems such as GPS. LAISYC significantly improves device battery life, provides location data authenticity, ensures security of location data, and significantly reduces the amount of data transferred between the phone and server. The design, implementation, and evaluation of LAISYC using real mobile phones include the following modules: the GPS Auto-Sleep module saves battery energy when using GPS, maintaining acceptable movement tracking (approximately 89% accuracy) with an approximate average doubling of battery life. …

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Reddy Varakantham, William Yeoh, Ajay Srinivasan, Hoong Chuin Lau, Shih-Fen Cheng

Research Collection School Of Computing and Information Systems

Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limits. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of …

Prioritized Shaping Of Models For Solving Dec-Pomdps, Pradeep Reddy Varakantham, William Yeoh, Prasanna Velagapudi, Paul Scerri

Research Collection School Of Computing and Information Systems

An interesting class of multi-agent POMDP planning problems can be solved by having agents iteratively solve individual POMDPs, find interactions with other individual plans, shape their transition and reward functions to encourage good interactions and discourage bad ones and then recompute a new plan. D-TREMOR showed that this approach can allow distributed planning for hundreds of agents. However, the quality and speed of the planning process depends on the prioritization scheme used. Lower priority agents shape their models with respect to the models of higher priority agents. In this paper, we introduce a new prioritization scheme that is guaranteed to …

Stochastic Dominance In Stochastic Dcops For Risk-Sensitive Applications, Nguyen Duc Thien, William Yeoh, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems where the primary interactions are between local subsets of agents. However, one limitation of DCOPs is the assumption that the constraint rewards are without uncertainty. Researchers have thus extended DCOPs to Stochastic DCOPs (SDCOPs), where rewards are sampled from known probability distribution reward functions, and introduced algorithms to find solutions with the largest expected reward. Unfortunately, such a solution might be very risky, that is, very likely to result in a poor reward. Thus, in this paper, we make three contributions: (1) we propose a stricter objective for …

Delayed Observation Planning In Partially Observable Domains, Pradeep Reddy Varakantham, Janusz Marecki

Research Collection School Of Computing and Information Systems

Traditional models for planning under uncertainty such as Markov Decision Processes (MDPs) or Partially Observable MDPs (POMDPs) assume that the observations about the results of agent actions are instantly available to the agent. In so doing, they are no longer applicable to domains where observations are received with delays caused by temporary unavailability of information (e.g. delayed response of the market to a new product). To that end, we make the following key contributions towards solving Delayed observation POMDPs (D-POMDPs): (i) We first provide an parameterized approximate algorithm for solving D-POMDPs efficiently, with desired accuracy; and (ii) We then propose …

Multi-Tier Exploration Concept Demonstration Mission, Jeremy Straub

Jeremy Straub

A multi-tier, multi-craft mission architecture has been proposed but, despite its apparent promise, limited use and testing of the architecture has been conducted. This paper proposes and details a mission concept and its implementation for testing this architecture in the terrestrial environment. It is expected that this testing will allow significant refinement of the proposed architecture as well as providing data on its suitability for use in both terrestrial and extra-terrestrial applications. Logistical and technical challenges with this testing are discussed.

The Interacting Multiple Models Algorithm With State-Dependent Value Assignment, Rastin Rastgoufard

University of New Orleans Theses and Dissertations

The value of a state is a measure of its worth, so that, for example, waypoints have high value and regions inside of obstacles have very small value. We propose two methods of incorporating world information as state-dependent modifications to the interacting multiple models (IMM) algorithm, and then we use a game's player-controlled trajectories as ground truths to compare the normal IMM algorithm to versions with our proposed modifications. The two methods involve modifying the model probabilities in the update step and modifying the transition probability matrix in the mixing step based on the assigned values of different target states. …

Message Passing Algorithms For Map Estimation Using Dc Programming, Akshat Kumar, Shlomo Zilberstein, Marc Toussaint

Research Collection School Of Computing and Information Systems

We address the problem of finding the most likely assignment or MAP estimation in a Markov random field. We analyze the linear programming formulation of MAP through the lens of difference of convex functions (DC) programming, and use the concave-convex procedure (CCCP) to develop efficient message-passing solvers. The resulting algorithms are guaranteed to converge to a global optimum of the well-studied local polytope, an outer bound on the MAP marginal polytope. To tighten the outer bound, we show how to combine it with the mean-field based inner bound and, again, solve it using CCCP. We also identify a useful relationship …

Provable De-Anonymization Of Large Datasets With Sparse Dimensions, Anupam Datta, Divya Sharma, Arunesh Sinha

Research Collection School Of Computing and Information Systems

There is a significant body of empirical work on statistical de-anonymization attacks against databases containing micro-dataabout individuals, e.g., their preferences, movie ratings, or transactiondata. Our goal is to analytically explain why such attacks work. Specifically, we analyze a variant of the Narayanan-Shmatikov algorithm thatwas used to effectively de-anonymize the Netflix database of movie ratings. We prove theorems characterizing mathematical properties of thedatabase and the auxiliary information available to the adversary thatenable two classes of privacy attacks. In the first attack, the adversarysuccessfully identifies the individual about whom she possesses auxiliaryinformation (an isolation attack). In the second attack, the adversarylearns additional …

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

Dr Xiaoxun Sun

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 …

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …

Adaptive Algorithms For Coverage Control And Space Partitioning In Mobile Robotic Networks, Jerome Le Ny, George J. Pappas

George J. Pappas

We consider deployment problems where a mobile robotic network must optimize its configuration in a distributed way in order to minimize a steady-state cost function that depends on the spatial distribution of certain probabilistic events of interest. Three classes of problems are discussed in detail: coverage control problems, spatial partitioning problems, and dynamic vehicle routing problems. Moreover, we assume that the event distribution is a priori unknown, and can only be progressively inferred from the observation of the location of the actual event occurrences. For each problem we present distributed stochastic gradient algorithms that optimize the performance objective. The stochastic …