Vikas Shivashankar

ICAPS Conference 2023 Conference Paper

Deadline-Aware Multi-Agent Tour Planning

• Taoan Huang
• Vikas Shivashankar
• Michael Caldara
• Joseph W. Durham
• Jiaoyang Li 0001
• Bistra Dilkina
• Sven Koenig

The increasing demand for same-day delivery and the commitment of e-commerce companies to this service raise a number of challenges in logistics. One of these challenges for fulfillment centers is to coordinate hundreds of mobile robots in their automated warehouses efficiently to allow for the retrieval and packing of thousands of ordered items within the promised delivery deadlines. We formulate this challenge as the new problem of deadline-aware multi-agent tour planning, where the objective is to coordinate robots to visit multiple picking stations in congested warehouses to allow as many orders to be packed on time as possible. To solve it, we propose LaRge NeighbOrhood Search for DEadline-Aware MulTi-Agent Tour PlAnning (ROSETTA). We conduct extensive experiments to evaluate ROSETTA with up to 350 robots in simulated warehouses inspired by KIVA systems. We show that it increases the number of orders completed on time by up to 38% compared to several baseline algorithms and also significantly outperforms them in terms of throughput and station utilization.

JAIR Journal 2018 Journal Article

Extending Classical Planning with State Constraints: Heuristics and Search for Optimal Planning

• Patrik Haslum
• Franc Ivankovic
• Miquel Ramirez
• Dan Gordon
• Sylvie Thiebaux
• Vikas Shivashankar
• Dana S. Nau

We present a principled way of extending a classical AI planning formalism with systems of state constraints, which relate - sometimes determine - the values of variables in each state traversed by the plan. This extension occupies an attractive middle ground between expressivity and complexity. It enables modelling a new range of problems, as well as formulating more efficient models of classical planning problems. An example of the former is planning-based control of networked physical systems - power networks, for example - in which a local, discrete control action can have global effects on continuous quantities, such as altering flows across the entire network. At the same time, our extension remains decidable as long as the satisfiability of sets of state constraints is decidable, including in the presence of numeric state variables, and we demonstrate that effective techniques for cost-optimal planning known in the classical setting - in particular, relaxation-based admissible heuristics - can be adapted to the extended formalism. In this paper, we apply our approach to constraints in the form of linear or non-linear equations over numeric state variables, but the approach is independent of the type of state constraints, as long as there exists a procedure that decides their consistency. The planner and the constraint solver interact through a well-defined, narrow interface, in which the solver requires no specialisation to the planning context.

AAAI Conference 2017 Conference Paper

Incorporating Domain-Independent Planning Heuristics in Hierarchical Planning

• Vikas Shivashankar
• Ron Alford
• David Aha

Heuristics serve as a powerful tool in modern domainindependent planning (DIP) systems by providing critical guidance during the search for high-quality solutions. However, they have not been broadly used with hierarchical planning techniques, which are more expressive and tend to scale better in complex domains by exploiting additional domainspecific knowledge. Complicating matters, we show that for Hierarchical Goal Network (HGN) planning, a goal-based hierarchical planning formalism that we focus on in this paper, any poly-time heuristic that is derived from a deleterelaxation DIP heuristic has to make some relaxation of the hierarchical semantics. To address this, we present a principled framework for incorporating DIP heuristics into HGN planning using a simple relaxation of the HGN semantics we call Hierarchy-Relaxation. This framework allows for computing heuristic estimates of HGN problems using any DIP heuristic in an admissibility-preserving manner. We demonstrate the feasibility of this approach by using the LMCut heuristic to guide an optimal HGN planner. Our empirical results with three benchmark domains demonstrate that simultaneously leveraging hierarchical knowledge and heuristic guidance substantially improves planning performance.

ECAI Conference 2016 Conference Paper

Cost-Optimal Algorithms for Planning with Procedural Control Knowledge

• Vikas Shivashankar
• Ron Alford
• Mark Roberts
• David W. Aha

IJCAI Conference 2016 Conference Paper

Hierarchical Planning: Relating Task and Goal Decomposition with Task Sharing

• Ron Alford
• Vikas Shivashankar
• Mark Roberts
• Jeremy Frank
• David W. Aha

Considerable work has focused on enhancing the semantics of Hierarchical Task Networks (HTNs) in order to advance the state-of-the-art in hierarchical planning. For instance, the Hierarchical Goal Netwwork (HGN) formalism operates over a hierarchy of goals to facilitate tighter integration of decompositional planning with classical planning. Another example is the Action Notation Markup Language (ANML) which adds aspects of generative planning and task-sharing to the standard HTN semantics. The aim of this work is to formally analyze the effects of these modifications to HTN semantics on the computational complexity and expressivity of HTN planning. To facilitate analysis, we unify goal and task planning into Goal-Task Network (GTN) planning. GTN models use HTN and HGN constructs, but have a solution-preserving mapping back to HTN planning. We then show theoretical results that provide new insights into both the expressivity as well as computational complexity of GTN planning under a number of different semantics. Our work lays a firm footing to clarify exact semantics for recent planners based on ANML, HGNs, and similar hierarchical languages.

ICAPS Conference 2014 Conference Paper

On the Feasibility of Planning Graph Style Heuristics for HTN Planning

• Ron Alford
• Vikas Shivashankar
• Ugur Kuter
• Dana S. Nau

In classical planning, the polynomial-time computability of propositional delete-free planning (planning with only positive effects and preconditions) led to the highly successful Relaxed Graphplan heuristic. We present a hierarchy of new computational complexity results for different classes of propositional delete-free HTN planning, with two main results: We prove that finding a plan for the delete-relaxation of a propositional HTN problem is NP-complete: hence unless P=NP, there is no directly analogous GraphPlan heuristic for HTN planning. However, a further relaxation of HTN planning (delete-free HTN planning with task insertion) is polynomial-time computable. Thus, there may be a possibility of using this or other relaxations to develop search heuristics for HTN planning.

ICAPS Conference 2014 Conference Paper

Optimal Planning with Global Numerical State Constraints

• Franc Ivankovic
• Patrik Haslum
• Sylvie Thiébaux
• Vikas Shivashankar
• Dana S. Nau

Automating the operations of infrastructure networks such as energy grids and oil pipelines requires a range of planning and optimisation technologies. However, current planners face significant challenges in responding to this need. Notably, they are unable to model and reason about the global numerical state constraints necessary to capture flows and similar physical phenomena occurring in these networks. A single discrete control action can affect the flow throughout the network in a way that may depend on the entire network topology. Determining whether preconditions, goals and invariant conditions are satisfied requires solving a system of numerical constraints after each action application. This paper extends domain-independent optimal planning to this kind of reasoning. We present extensions of the formalism, relaxed plans, and heuristics, as well as new search variants and experimental results on two problem domains.

IJCAI Conference 2013 Conference Paper

The GoDeL Planning System: A More Perfect Union of Domain-Independent and Hierarchical Planning

• Vikas Shivashankar
• Ron Alford
• Ugur Kuter
• Dana Nau

One drawback of Hierarchical Task Network (HTN) planning is the difficulty of providing complete domain knowledge, i. e. , a complete and correct set of HTN methods for every task. To provide a principled way to overcome this difficulty, we define a simple formalism that extends classical planning to include problem decomposition using methods, and a planning algorithm based on this formalism. In our formalism, the methods specify ways to achieve goals (rather than tasks as in conventional HTN planning), and goals may be achieved even when no methods are available. Our planning algorithm, GoDeL (Goal Decomposition with Landmarks), is sound and complete irrespective of whether the domain knowledge (i. e. , the set of methods given to the planner) is complete. By comparing GoDeL’s performance with varying amounts of domain knowledge across three benchmark planning domains, we show experimentally that (1) GoDeL works correctly with partial planning knowledge, (2) GoDeL’s performance improves as more planning knowledge is given, and (3) when given full domain knowledge, GoDeL matches the performance of a state-of-the-art hierarchical planner.

AAMAS Conference 2012 Conference Paper

A Hierarchical Goal-Based Formalism and Algorithm for Single-Agent Planning

• Vikas Shivashankar
• Ugur Kuter
• Dana Nau
• Ron Alford

Plan generation is important in a number of agent applications, but such applications generally require elaborate domain models that include not only the definitions of the actions that an agent can perform in a given domain, but also information about the most effective ways to generate plans for the agent in that domain. Such models typically take a large amount of human effort to create. To alleviate this problem, we have developed a hierarchical goal-based planning formalism and a planning algorithm, GDP (Goal-Decomposition Planner), that combines some aspects of both HTN planning and domain-independent planning. For example, it allows the planning agent to use domain-independent heuristic functions to guide the application of both methods and actions. This paper describes the formalism, planning algorithm, correctness theorems, and the results of a large experimental study. The experiments show that our planning algorithm works as well as the well-known SHOP2 HTN planner, using domain models only about half the size of SHOP2's.

SoCS Conference 2012 Conference Paper

HTN Problem Spaces: Structure, Algorithms, Termination

• Ron Alford
• Vikas Shivashankar
• Ugur Kuter
• Dana S. Nau

For HTN planning, we formally characterize and classify four kinds of problem spaces in which each node represents a planning problem or subproblem. Two of the problem spaces are searched by current HTN planning algorithms; the other two problem spaces are new. This enables us to provide: Sufficient (and in one case, necessary) conditions for finiteness of each kind of problem space. The conditions can be evaluated up-front to see if an HTN planning problem is finite. Loop-detection tests that can be used in HTN planners to ensure termination when the problem space is finite. A way to compute the correct value for an upper-bound parameter in an HTN-to-PDDL translation algorithm published in IJCAI-2009. Planning algorithms that utilize the two new problem spaces to guarantee termination on broader classes of planning problems than previous HTN planning algorithms.

ECAI Conference 2010 Conference Paper

A Fault-model-based Debugging Aid for Data Warehouse Applications

• Peter Struss
• Vikas Shivashankar
• Mohamed Zahoor

The paper describes a model-based approach to developing a general tool for localizing faults in applications of data warehouse technology. A model of the application is configured from a library of generic models of standard (types of) modules and exploited by a consistency-based diagnosis algorithm, originally used for diagnosing physical devices. Observing intermediate results can require high efforts or even be impossible, which limits the discriminability between different faults in a sequence of data processing steps. To compensate for this, fault models are used. This becomes a feasible solution for standard modules of a data warehouse application along with a stratification of the data. Fault models capture the potential impact of faults of process steps and data transfer on the data strata as well as on sets of data. Reflecting the nature of the initial symptoms and of the potential checks, these descriptions are stated at a qualitative level. The solution has been validated in customer report generation of a provider of mobile phone services.