Open Access. Powered by Scholars. Published by Universities.®
Artificial Intelligence and Robotics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Uncertainty (4)
- Urban Transportation (3)
- Multi-agent decision making (2)
- Urban transportation (2)
- Auction (1)
-
- Commodity Trading (1)
- Computational Economy (1)
- Consumer behaviour (1)
- Cost sharing (1)
- Digital simulation (1)
- Driver behavior (1)
- Electronic Market (1)
- Lagrangian Relaxation (1)
- Market-based approach (1)
- Market-based resource allocation (1)
- Mechanism design (1)
- Mobility pattern (1)
- Multi-agent Planning (1)
- Multi-agent systems (1)
- Multiagent simulation (1)
- Ride sharing (1)
- Ride sharing mechanism (1)
- Robust resource allocation (1)
- Robustness (1)
- Scheduling (1)
- Taxi fleet (1)
- Travel industry (1)
Articles 1 - 22 of 22
Full-Text Articles in Artificial Intelligence and Robotics
Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau
Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau
Shih-Fen CHENG
In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation …
Budgeted Personalized Incentive Approaches For Smoothing Congestion In Resource Networks, Pradeep Varakantham, Na Fu, William Yeoh, Shih-Fen Cheng, Hoong Chuin Lau
Budgeted Personalized Incentive Approaches For Smoothing Congestion In Resource Networks, Pradeep Varakantham, Na Fu, William Yeoh, Shih-Fen Cheng, Hoong Chuin Lau
Shih-Fen CHENG
Congestion occurs when there is competition for resources by sel sh agents. In this paper, we are concerned with smoothing out congestion in a network of resources by using personalized well-timed in- centives that are subject to budget constraints. To that end, we provide: (i) a mathematical formulation that computes equilibrium for the re- source sharing congestion game with incentives and budget constraints; (ii) an integrated approach that scales to larger problems by exploiting the factored network structure and approximating the attained equilib- rium; (iii) an iterative best response algorithm for solving the uncon- strained version (no budget) of the …
Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau
Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau
Shih-Fen CHENG
The Orienteering Problem (OP), as originally defined by Tsiligirides, is the problem of cross-countr sport in which participants get rewards from visiting a predefined set of checkpoints. As Orienteering Problem can be used to describe a wide variety of real-world problems like route planning for facility inspection, patrolling of strategic location, and reward-weighted traveling salesman problem, it has attracted continuous interests from researchers and a large number of variants and corresponding algorithms for solving them have been introduced.
Mechanisms For Arranging Ride Sharing And Fare Splitting For Last-Mile Travel Demands, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau
Mechanisms For Arranging Ride Sharing And Fare Splitting For Last-Mile Travel Demands, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau
Shih-Fen CHENG
A great challenge of city planners is to provide efficient and effective connection service to travelers using public transportation system. This is commonly known as the last-mile problem and is critical in promoting the utilization of public transportation system. In this paper, we address the last-mile problem by considering a dynamic and demand-responsive mechanism for arranging ride sharing on a non-dedicated commercial fleet (such as taxis or passenger vans). Our approach has the benefits of being dynamic, flexible, and with low setup cost. A critical issue in such ride-sharing service is how riders should be grouped and serviced, and how …
A Multi-Objective Memetic Algorithm For Vehicle Resource Allocation In Sustainable Transportation Planning, Hoong Chuin Lau, Lucas Agussurja, Shih-Fen Cheng, Pang Jin Tan
A Multi-Objective Memetic Algorithm For Vehicle Resource Allocation In Sustainable Transportation Planning, Hoong Chuin Lau, Lucas Agussurja, Shih-Fen Cheng, Pang Jin Tan
Shih-Fen CHENG
Sustainable supply chain management has been an increasingly important topic of research in recent years. At the strategic level, there are computational models which study supply and distribution networks with environmental considerations. At the operational level, there are, for example, routing and scheduling models which are constrained by carbon emissions. Our paper explores work in tactical planning with regards to vehicle resource allocation from distribution centers to customer locations in a multi-echelon logistics network. We formulate the bi-objective optimization problem exactly and design a memetic algorithm to efficiently derive an approximate Pareto front. We illustrate the applicability of our approach …
An Agent-Based Simulation Approach To Experience Management In Theme Parks, Shih-Fen Cheng, Larry Junjie Lin, Jiali Du, Hoong Chuin Lau, Pradeep Reddy Varakantham
An Agent-Based Simulation Approach To Experience Management In Theme Parks, Shih-Fen Cheng, Larry Junjie Lin, Jiali Du, Hoong Chuin Lau, Pradeep Reddy Varakantham
Shih-Fen CHENG
In this paper, we illustrate how massive agent-based simulation can be used to investigate an exciting new application domain of experience management in theme parks, which covers topics like congestion control, incentive design, and revenue management. Since all visitors are heterogeneous and self-interested, we argue that a high-quality agent-based simulation is necessary for studying various problems related to experience management. As in most agent-base simulations, a sound understanding of micro-level behaviors is essential to construct high-quality models. To achieve this, we designed and conducted a first-of-its-kind real-world experiment that helps us understand how typical visitors behave in a theme-park environment. …
Interacting Knapsack Problem In Designing Resource Bundles, Truong Huy D. Nguyen, Pradeep Reddy Varakantham, Hoong Chuin Lau, Shih-Fen Cheng
Interacting Knapsack Problem In Designing Resource Bundles, Truong Huy D. Nguyen, Pradeep Reddy Varakantham, Hoong Chuin Lau, Shih-Fen Cheng
Shih-Fen CHENG
In many real-life businesses, the service provider/seller keeps a log of the visitors’ behavior as a way to assess the efficiency of the current business/operation model and find room for improvement. For example, by tracking when visitors entering attractions in a theme park, theme park owners can detect when and where congestion may occur, thus having contingency plans to reroute the visitors accordingly. Similarly, a Cable TV service provider can track channel switching events at each household to identify uninteresting channels. Subsequently, the repertoire of channels up for subscription can evolve over time to better serve the entertainment demand of …
Uncertain Congestion Games With Assorted Human Agent Populations, Asrar Ahmed, Pradeep Reddy Varakantham, Shih-Fen Cheng
Uncertain Congestion Games With Assorted Human Agent Populations, Asrar Ahmed, Pradeep Reddy Varakantham, Shih-Fen Cheng
Shih-Fen CHENG
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 …
Decentralized Decision Support For An Agent Population In Dynamic And Uncertain Domains, Pradeep Reddy Varakantham, Shih-Fen Cheng, Thi Duong Nguyen
Decentralized Decision Support For An Agent Population In Dynamic And Uncertain Domains, Pradeep Reddy Varakantham, Shih-Fen Cheng, Thi Duong Nguyen
Shih-Fen CHENG
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 …
Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Reddy Varakantham, William Yeoh, Ajay Srinivasan, Hoong Chuin Lau, Shih-Fen Cheng
Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoff Gordon, Pradeep Reddy Varakantham, William Yeoh, Ajay Srinivasan, Hoong Chuin Lau, Shih-Fen Cheng
Shih-Fen CHENG
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 …
Notes On Equilibria In Symmetric Games, Shih-Fen Cheng, Daniel M. Reeves, Yevgeniy Vorobeychik, Michael P. Wellman
Notes On Equilibria In Symmetric Games, Shih-Fen Cheng, Daniel M. Reeves, Yevgeniy Vorobeychik, Michael P. Wellman
Shih-Fen CHENG
In a symmetric game, every player is identical with respect to the game rules. We show that a symmetric 2strategy game must have a pure-strategy Nash equilibrium. We also discuss Nash’s original paper and its generalized notion of symmetry in games. As a special case of Nash’s theorem, any finite symmetric game has a symmetric Nash equilibrium. Furthermore, symmetric infinite games with compact, convex strategy spaces and continuous, quasiconcave utility functions have symmetric pure-strategy Nash equilibria. Finally, we discuss how to exploit symmetry for more efficient methods of finding Nash equilibria.
Distributing Complementary Resources Across Multiple Periods With Stochastic Demand, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau
Distributing Complementary Resources Across Multiple Periods With Stochastic Demand, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau
Shih-Fen CHENG
In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments, we show that under stochastic conditions the performance variation of the process decreases as the time frame length (time …
Designing The Market Game For A Commodity Trading Simulation, Shih-Fen Cheng
Designing The Market Game For A Commodity Trading Simulation, Shih-Fen Cheng
Shih-Fen CHENG
In this paper, we propose to design a market game that (a) can be used in modeling and studying commodity trading scenarios, and (b) can be used in capturing human traders' behaviors. Specifically, we demonstrate the usefulness of this commodity trading game in a single-commodity futures trading scenario. A pilot experiment was run with a mixture of human traders and an autonomous agent that emulates the aggregatedmarket condition, with the assumption that this autonomous agent would hint each of its action through a public announcement. We show that the information collected from this simulation can be used to extract the …
Would Price Limits Have Made Any Difference To The 'Flash Crash' On May 6, 2010, Wing Bernard Lee, Shih-Fen Cheng, Annie Koh
Would Price Limits Have Made Any Difference To The 'Flash Crash' On May 6, 2010, Wing Bernard Lee, Shih-Fen Cheng, Annie Koh
Shih-Fen CHENG
On May 6, 2010, the U.S. equity markets experienced a brief but highly unusual drop in prices across a number of stocks and indices. The Dow Jones Industrial Average (see Figure 1) fell by approximately 9% in a matter of minutes, and several stocks were traded down sharply before recovering a short time later. The authors contend that the events of May 6, 2010 exhibit patterns consistent with the type of "flash crash" observed in their earlier study (2010). This paper describes the results of nine different simulations created by using a large-scale computer model to reconstruct the critical elements …
An Analysis Of Extreme Price Shocks And Illiquidity Among Trend Followers, Bernard Lee, Shih-Fen Cheng, Annie Koh
An Analysis Of Extreme Price Shocks And Illiquidity Among Trend Followers, Bernard Lee, Shih-Fen Cheng, Annie Koh
Shih-Fen CHENG
We construct an agent-based model to study the interplay between extreme price shocks and illiquidity in the presence of systematic traders known as trend followers. The agent-based approach is particularly attractive in modeling commodity markets because the approach allows for the explicit modeling of production, capacities, and storage constraints. Our study begins by using the price stream from a market simulation involving human participants and studies the behavior of various trend-following strategies, assuming initially that their participation will not impact the market. We notice an incremental deterioration in strategy performance as and when strategies deviate further and further from the …
A Mechanism For Organizing Last-Mile Service Using Non-Dedicated Fleet, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau
A Mechanism For Organizing Last-Mile Service Using Non-Dedicated Fleet, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau
Shih-Fen CHENG
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 …
An Agent-Based Commodity Trading Simulation, Shih-Fen Cheng, Yee Pin Lim
An Agent-Based Commodity Trading Simulation, Shih-Fen Cheng, Yee Pin Lim
Shih-Fen CHENG
In this paper, an event-centric commodity trading simulation powered by the multiagent framework is presented. The purpose of this simulation platform is for training novice traders. The simulation is progressed by announcing news events that affect various aspects of the commodity supply chain. Upon receiving these events, market agents that play the roles of producers, consumers, and speculators would adjust their views on the market and act accordingly. Their actions would be based on their roles and also their private information, and collectively they shape the market dynamics. This simulation has been effectively deployed for several training sessions. We will …
Iterated Weaker-Than-Weak Dominance, Shih-Fen Cheng, Michael P. Wellman
Iterated Weaker-Than-Weak Dominance, Shih-Fen Cheng, Michael P. Wellman
Shih-Fen CHENG
We introduce a weakening of standard gametheoretic δ-dominance conditions, called dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a δ-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter. We can apply elimination of δ-dominated strategies iteratively, but the for which a strategy may be eliminated depends on prior eliminations. We discuss implications of this order independence, and propose greedy heuristics for determining a sequence of eliminations to reduce the game as far as possible …
Multi-Period Combinatorial Auction Mechanism For Distributed Resource Allocation And Scheduling, Hoong Chuin Lau, Shih-Fen Cheng, Thin Yin Leong, Jong Han Park, Zhengyi Zhao
Multi-Period Combinatorial Auction Mechanism For Distributed Resource Allocation And Scheduling, Hoong Chuin Lau, Shih-Fen Cheng, Thin Yin Leong, Jong Han Park, Zhengyi Zhao
Shih-Fen CHENG
We consider the problem of resource allocation and scheduling where information and decisions are decentralized, and our goal is to propose a market mechanism that allows resources from a central resource pool to be allocated to distributed decision makers (agents) that seek to optimize their respective scheduling goals. We propose a generic combinatorial auction mechanism that allows agents to competitively bid for the resources needed in a multi-period setting, regardless of the respective scheduling problem faced by the agent, and show how agents can design optimal bidding strategies to respond to price adjustment strategies from the auctioneer. We apply our …
Uncertain Congestion Games With Assorted Human Agent Populations, Pradeep Reddy Varakantham, Asrar Ahmed, Shih-Fen Cheng
Uncertain Congestion Games With Assorted Human Agent Populations, Pradeep Reddy Varakantham, Asrar Ahmed, Shih-Fen Cheng
Shih-Fen CHENG
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 …
Decision Support For Agent Populations In Uncertain And Congested Environments, Pradeep Reddy Varakantham, Shih-Fen Cheng, Geoff Gordon, Asrar Ahmed
Decision Support For Agent Populations In Uncertain And Congested Environments, Pradeep Reddy Varakantham, Shih-Fen Cheng, Geoff Gordon, Asrar Ahmed
Shih-Fen CHENG
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, …
Taxisim: A Multiagent Simulation Platform For Evaluating Taxi Fleet Operations, Shih-Fen Cheng, Thi Duong Nguyen
Taxisim: A Multiagent Simulation Platform For Evaluating Taxi Fleet Operations, Shih-Fen Cheng, Thi Duong Nguyen
Shih-Fen CHENG
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 …