Author name cluster

Laura Barbulescu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AAAI Conference 2012 Conference Paper

Incremental Management of Oversubscribed Vehicle Schedules in Dynamic Dial-A-Ride Problems

Zachary Rubinstein
Stephen Smith
Laura Barbulescu

In this paper, we consider the problem of feasibly integrating new pick-up and delivery requests into existing vehicle itineraries in a dynamic, dial-a-ride problem (DARP) setting. Generalizing from previous work in oversubscribed task scheduling, we define a controlled iterative repair search procedure for finding an alternative set of vehicle itineraries in which the overall solution has been feasibly extended to include newly received requests. We first evaluate the performance of this technique on a set of DARP feasibility benchmark problems from the literature. We then consider its use on a real-world DARP problem, where it is necessary to accommodate all requests and constraints must be relaxed when a request cannot be feasibly integrated. For this latter analysis, we introduce a constraint relaxation post processing step and consider the performance impact of using our controlled iterative search over the current greedy search approach.

PDF Details

AAMAS Conference 2010 Conference Paper

Distributed Coordination of Mobile Agent Teams: The Advantage of Planning Ahead

Laura Barbulescu
Zachary Rubinstein
Stephen Smith
Terry Zimmerman

We consider the problem of coordinating a team of agentsengaged in executing a set of inter-dependent, geographicallydispersed tasks in an oversubscribed and uncertain environment. In such domains, where there are sequence-dependentsetup activities (e. g. , travel), we argue that there is inherent leverage to having agents maintain advance schedules. In the distributed problem solving setting we consider, eachagent begins with a task itinerary, and, as execution unfolds and dynamics ensue (e. g. , tasks fail, new tasks are discovered, etc. ), agents must coordinate to extend and revisetheir plans accordingly. The team objective is to maximizethe utility accrued from executed actions over a given timehorizon. Our approach to solving this problem is based ondistributed management of agent schedules. We describe anagent architecture that uses the synergy between intra-agentscheduling and inter-agent coordination to promote task allocation decisions that minimize travel time and maximizetime available for utility-acrruing activities. Experimentalresults are presented that compare our agent's performanceto that of an agent using an intelligent dispatching strategypreviously shown to outperform our approach on synthetic, stateless, utility maximization problems. Across a range ofproblems involving a mix of situated and non-situated tasksour advance scheduling approach dominates this same dispatch strategy. Finally, we report performance results withan extension of the system on a limited set of field test experiments.

PDF

AAMAS Conference 2007 Conference Paper

Distributed Management of Flexible Times Schedules

Stephen F. Smith
Anthony Gallagher
Terry Zimmerman
Laura Barbulescu
Zachary Rubinstein

We consider the problem of managing schedules in an uncertain, distributed environment. We assume a team of collaborative agents, each responsible for executing a portion of a globally pre-established schedule, but none possessing a global view of either the problem or solution. The goal is to maximize the joint quality obtained from the activities executed by all agents, given that, during execution, unexpected events will force changes to some prescribed activities and reduce the utility of executing others. We describe an agent architecture for solving this problem that couples two basic mechanisms: (1) a "flexible times" representation of the agent's schedule (using a Simple Temporal Network) and (2) an incremental rescheduling procedure. The former hedges against temporal uncertainty by allowing execution to proceed from a set of feasible solutions, and the latter acts to revise the agent's schedule when execution is forced outside of this set of solutions or when execution events reduce the expected value of this feasible solution set. Basic coordination with other agents is achieved simply by communicating schedule changes to those agents with inter-dependent activities. Then, as time permits, the core local problem solving infra-structure is used to drive an inter-agent option generation and query process, aimed at identifying opportunities for solution improvement through joint change. Using a simulator to model the environment, we compare the performance of our multi-agent system with that of an expected optimal (but non-scalable) centralized MDP solver.

PDF

AAAI Conference 2004 Conference Paper

Leap Before You Look: An Effective Strategy in an Oversubscribed Scheduling Problem

Laura Barbulescu

Oversubscribed scheduling problems require removing or partially satisfying tasks when enough resources are not available. For a particular oversubscribed problem, Air Force Satellite Control Network scheduling, we find that the best approaches make long leaps in the search space. We find this is in part due to large plateaus in the search space. Algorithms moving only one task at a time are impractical. Both a genetic algorithm and Squeaky Wheel Optimization (SWO) make long leaps in the search space and produce good solutions almost 100 times faster than local search. Greedy initialization is shown to be critical to good performance, but is not as important as directed leaps. When using fewer than 2000 evaluations, SWO shows superior performance; with 8000 evaluations, a genetic algorithm using a population seeded with greedy solutions further improves on the SWO results.

PDF Details

ICAPS Conference 2004 Conference Paper

Trading Places: How to Schedule More in a Multi-Resource Oversubscribed Scheduling Problem

Laura Barbulescu
Adele E. Howe
L. Darrell Whitley
Mark Roberts

Oversubscribed scheduling problems require removing tasks when enough resources are not available. Prior AI approaches have mostly been constructive or repairbased heuristic search. In contrast, we have found a genetic algorithm (GA) to be the best approach to the overconstrained problem of Air Force Satellite Control Network scheduling. We present empirical results that elucidate sources of difficulty in the application and partially explain why the GA is well suited to this problem. We show that the task interaction compels changes involving many tasks simultaneously and the GA appears to be learning domain specific patterns in the data.

Details

AAAI Conference 2000 Conference Paper

Dynamic Representations and Escaping Local Optima: Improving Genetic Algorithms and Local Search

Laura Barbulescu
and L. Darrell Whitley

Local search algorithms often get trapped in local optima. Algorithms such as tabu search and simulated annealing ’escape’ local optima by accepting nonimproving moves. Another possibility is to dynamically change between representations; a local optimum under one representation may not be a local optimum under another. Shifting is a mechanism which dynamically switches between Gray code representations in order to escape local optima. Gray codes are widely used in conjunction with genetic algorithms and bit-climbing algorithms for parameter optimization problems. We present new theoretical results that substantially improve our understanding of the shifting mechanism, on the number of Gray codes accessible via shifting, and on how neighborhood structure changes during shifting. We show that shifting can significantly improve the performance of a simple hill-climber; it can also help to improve one of the best genetic algorithms currently available.

PDF Details

AAAI Conference 1999 Conference Paper

Algorithms Performance and Problem Structure for Flow-Shop Scheduling

Jean-Paul Watson
Laura Barbulescu
Adele E. Howe
L. Darrell Whitley
Colorado State University Search

Test suites for many domains often fail to model features present in real-world problems. For the permutation flow-shop sequencing problem (PFSP), the most popular test suite consists of problems whose features are generated from a single uniform random distribution. Synthetic generation of problems with characteristics present in real-world problems is a viable alternative. We compare the performance of several competitive algorithms on problems produced with such a generator. We find that, as more realistic characteristics are introduced, the performance of a stateof-the-art algorithm degrades rapidly: faster and less complex stochastic algorithms provide superior performance. Our empirical results show that small changes in problem structure or problem size can influence algorithm performance. We hypothesize that these performance differences may be partially due to differences in search space topologies; we show that structured problems produce topologies with performance plateaus. Algorithm sensitivity to problem characteristics suggests the need to construct test suites more representative of real-world applications.

PDF Details