Richard Goodwin

AAAI Conference 2006 System Paper

SEMAPLAN: Combining Planning with Semantic Matching to Achieve Web Service Composition

• Rama Akkiraju
• Biplav Srivastava
• Richard Goodwin

In this paper, we present a novel algorithm to compose Web services in the presence of semantic ambiguity by combining semantic matching and AI planning algorithms. We use cues from domain-independent and domain-specific ontologies to compute an overall semantic similarity score between ambiguous terms. This semantic similarity score is used by AI planning algorithms to guide the searching process when composing services. Experimental results indicate that planning with semantic matching produces better results than planning or semantic matching alone. The solution is suitable for semi-automated composition tools or directory browsers.

ICAPS Conference 2006 Conference Paper

SEMAPLAN: Combining Planning with Semantic Matching to Achieve Web Service Composition

• Rama Akkiraju
• Biplav Srivastava
• Anca-Andreea Ivan
• Richard Goodwin
• Tanveer Fathima Syeda-Mahmood

Composing existing Web services to deliver new functionality is a difficult problem as it involves resolving semantic, syntactic and structural differences among the interfaces of a large number of services. Unlike most planning problems, it can not be assumed that Web services are described using terms from a single domain theory. While service descriptions may be controlled to some extent in restricted settings (e. g., intra-enterprise integration), in Web-scale open integration, lack of common, formalized service descriptions prevent the direct application of standard planning methods. In this paper, we present a novel algorithm to compose Web services in the presence of semantic ambiguity by combining semantic matching and AI planning algorithms. Specifically, we use cues from domain-independent and domain-specific ontologies to compute an overall semantic similarity score between ambiguous terms. This semantic similarity score is used by AI planning algorithms to guide the searching process when composing services. Experimental results indicate that planning with semantic matching produces better results than planning or semantic matching alone. The solution is suitable for semi-automated composition tools or directory browsers.

AAMAS Conference 2003 Conference Paper

Risk-Averse Auction Agents

• Yaxin Liu
• Richard Goodwin
• Sven Koenig

ICAPS Conference 1998 Conference Paper

Search Control of Plan Generation in Decision-Theoretic Planners

• Richard Goodwin
• Reid G. Simmons

This paper addresses the search control problemof selecting whichplan to refine next for decision-theoretic planners, a choice point common to the decision theoretic planners created to date. Such planners can makeuse of a utility function to calculate boundson the expectedutility of an abstract plan. Threestrategies for using these boundsto select the next plan to refine have been proposed in the literature. Weexaminethe rationale for each strategy and prove that the optimistic strategy of alwaysselecting a plan with the highest upper-boundon expected utility expands the fewest numberof plans, whenlooking for all plans with the highest expected utility. Whenlooking for a single plan with the highest expected utility, we prove that the optimistic strategy has the best possible worst case performanceand that other strategies can fail to terminate. To demonstratethe effect of plan selection strategies on performance, we give results using the DRWS planner that showthat the optimistic strategy can produce exponential improvements in time and space.

ICAPS Conference 1996 Conference Paper

Using Loops in Decision-Theoretic Refinement Planners

• Richard Goodwin

Classical AI planners use loops over subgoals to move a stack of blocks by repeatedly moving the top block. Probabilistic planners and reactive systems repeatedly try to pick up a block to increase the probability of success in an uncertain environment. These planners terminate a loop only when the goal is achieved or when the probability of success has reached some threshold. The tradeoff between the cost of repeating a loop and the expected benefit is ignored. Decision-theoretic refinement planners take this tradeoff into account, but to date, have been limited to considering only finite length plans. In this paper, we describe extensions to a decision-theoretic refinement planner, DRIPS, for handling loops. The extended planner terminates a loop when it can show that all plans with one or more additional iterations of the loop have lower utility. We give conditions under which optimal plans are finite and conditions under which the planner will find an optimal plan and terminate. With loops, a decision-theoretic refinement planner searches an infinite space of plans, making search control critical. We demonstrate how our sensitivity analysis-based search control technique provides effective search control without requiring the domain designer to hand-tune parameters, or otherwise provide search control information.

UAI Conference 1995 Conference Paper

Efficient Decision-Theoretic Planning: Techniques and Empirical Analysis

• Peter Haddawy
• AnHai Doan
• Richard Goodwin

This paper discusses techniques for performing efficient decision-theoretic planning. We give an overview of the DRIPS decision-theoretic refinement planning system, which uses abstraction to efficiently identify optimal plans. We present techniques for automatically generating search control information, which can significantly improve the planner's performance. We evaluate the efficiency of DRIPS both with and without the search control rules on a complex medical planning problem and compare its performance to that of a branch-and-bound decision tree algorithm.

IROS Conference 1995 Conference Paper

Experience with rover navigation for lunar-like terrains

• Reid G. Simmons
• Eric Krotkov
• Lonnie Chrisman
• Fábio Gagliardi Cozman
• Richard Goodwin
• Martial Hebert
• Lalitesh Katragadda
• Sven Koenig

Reliable navigation is critical for a lunar rover, both for autonomous traverses and safeguarded remote teleoperation. This paper describes an implemented system that has autonomously driven a prototype wheeled lunar rover over a kilometer in natural, outdoor terrain. The navigation system uses stereo terrain maps to perform local obstacle avoidance, and arbitrates steering recommendations from both the user and the rover. The paper describes the system architecture, each of the major components, and the experimental results to date.

AAAI Conference 1994 Short Paper

Reasoning about What to Plan

• Richard Goodwin

Agents plan in order to improve their performance. However, planning takes time and consumes resources that may in fact degrade an agents performance. Ideally, an agent should only plan when the expected improvement outweighs the expected cost and no resources should be expended on making this decision. To do this, an agent would have to be omniscient. The problem of how to approximate this ideal, without consuming too many resources in the process, is the meta-level control problem for a resource bounded rational agent.

ICAPS Conference 1994 Conference Paper

Reasoning About When to Start Acting

• Richard Goodwin

Facedwith a complicatedtask, someinitial planningcan significantlyincreasethe likelihoodof successandincrease efficiency, but planningfor too long beforestarting to act can reduceefficiency. Thispaper exploresthe questionof whento begin acting for a resourceboundedagent. Limitations of an idealizedalgorithmsuggestedin the literature are presentedandillustrated in the contextof a robotcourier. A revised, idealizedalgorithmis givenandjustified. Therevised idealizedalgorithmis usedas a basis for developinga new"step choice"algorithmfor makingon-the-flydecisions for a simplifiedversionof the robot courier task. Aset of experimentsare usedto illustrate the relative advantageof the newstrategy over alwaysact, alwayscomputeand anytime algorithmbasedstrategies for decidingwhento begin execution.