Author name cluster

Mark Boddy

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.

5 papers

1 author row

AAAI Conference 2011 Conference Paper

Bayesian Learning of Generalized Board Positions for Improved Move Prediction in Computer Go

Martin Michalowski
Mark Boddy
Mike Neilsen

Computer Go presents a challenging problem for machine learning agents. With the number of possible board states estimated to be larger than the number of hydrogen atoms in the universe, learning effective policies or board evaluation functions is extremely difﬁcult. In this paper we describe Cortigo, a system that efﬁciently and autonomously learns useful generalizations for large state-space classiﬁcation problems such as Go. Cortigo uses a hierarchical generative model loosely related to the human visual cortex to recognize Go board positions well enough to suggest promising next moves. We begin by brieﬂy describing and providing motivation for research in the computer Go domain. We describe Cortigo’s ability to learn predictive models based on large subsets of the Go board and demonstrate how using Cortigo’s learned models as additive knowledge in a state-of-the-art computer Go player (Fuego) signiﬁcantly improves its playing strength.

PDF Details

AIJ Journal 1994 Journal Article

Deliberation scheduling for problem solving in time-constrained environments

Mark Boddy
Thomas L Dean

We are interested in the problem faced by an agent with limited computational capabilities, embedded in a complex environment with other agents and processes not under its control. Careful management of computational resources is important for complex problem-solving tasks in which the time spent in decision making affects the quality of the responses generated by a system. This paper describes an approach to designing systems that are capable of taking their own computational resources into consideration during planning and problem solving. In particular, we address the design of systems that manage their computational resources by using expectations about the performance of decision-making procedures and preferences over the outcomes resulting from applying those procedures. Our approach is called deliberation scheduling. Deliberation scheduling involves the explicit allocation of computational resources to decision-making procedures based on the expected effect of those allocations on the system's performance.

Details DOI

AAAI Conference 1991 Conference Paper

Anytime Problem Solving Using Dynamic Programming

Mark Boddy

In previous work, we have advocated explicitly scheduling computation time for planning and problem solving (deliberetion) using a framework called ezpectation-driven iterative refinement. Within this framework, we have explored the problem of allocating deliberation time when the procedures used for deliberation implement anytime algorithms: algorithms that return some answer for any allocation of time. In our search for useful techniques for constructing anytime algorithms, we have discovered that dynemic programming shows considerable promise for the construction of anytime algorithms for a wide variety of problems. In this paper, we show how dynamic programming techniques can be used to construct useful anytime procedures for two problems: multiplying sequences of matrices, and the Travelling Salesman Problem. Dynamic programming can be applied to a wide variety of optimization and control problems, many of them relevant to current AI research (e. g. , scheduling, probabilistic reasoning, and controlling machinery). Being able to solve these kinds of problems using anytime procedures increases the range of problems to which expectation-driven iterative refinement can be applied.

PDF Details

IJCAI Conference 1989 Conference Paper

Solving Time-Dependent Planning Problems

Mark Boddy
Thomas Dean

A planning problem is time-dependent, if the time spent planning affects the utility of the system's performance. In [Dean and Boddy, 1988], we define a framework for constructing solutions to time-dependent planning problems, called expectation-driven iterative refinement. In this paper, we analyze and solve a moderately complex time-dependent planning problem involving path planning for a mobile robot, as a way of exploring a methodology for applying expectation-driven iterative refinement. The fact that we construct a solution to the proposed problem without appealing to luck or extraordinary inspiration provides evidence that expectation-driven iterative refinement is an appropriate framework for solving time-dependent planning problems.

PDF

AIJ Journal 1988 Journal Article

Reasoning about partially ordered events

Thomas Dean
Mark Boddy

This paper describes a class of temporal reasoning problems involving events whose order is not completely known. We examine the complexity of such problems and show that for all but trivial cases these problems are likely to be intractable. As an alternative to a complete, but potentially exponential-time decision procedure, we provide a partial decision procedure that reports useful results and runs in polynomial time.

Details DOI