Seminars in November, 1996
- 11/26/96 - Carbon vs. Silicon: Will machines ever think like we do? Matthew L. Ginsberg, CIRL, University of Oregon.
- 11/19/96 - Inferring Sequential Structure. Craig Nevill-Manning, Biochemistry University, Stanford Uinversity.
- 11/12/96 - Scaling the Dynamical Systems Approach to Path Planning: Competition among Behavioral Constraints. Edward Large, Department of Computer and Information Science University of Pennsylvania
- 11/05/96 - Model-checking Reliability and Performance Properties of Untimed and Timed Systems, Luca de Alfaro, Department of Computer Science, Stanford University.
Seminar Abstracts
Tuesday Nov 26,1996
4-5:30pm
306 Soda Hall
Carbon vs. Silicon: Will machines ever think like we do?
Matthew L. Ginsberg
CIRL, University of Oregon
Abstract:
This talk examines recent practical successes in artificial intelligence. In domains as diverse as automated scheduling, planning, game playing and natural language understanding, performance of practical value is obtained by exploiting the raw speed of machines, as opposed to their ability to think in ways similar to people.It is possible to think of common sense as the ability to solve in practice problems that are too difficult to solve exactly. Because the problems that machines can solve exactly, along with those that they cannot, are far different from those that can be solved by their human counterparts, the above observation has profound implications with regard to what constitutes "common sense" for man and machine. I will work from a variety of examples of successful AI systems to build a formal definition of common sense that can be applied to machines as well as to people, and then draw conclusions from this definition regarding the directions that should be taken by basic work in AI at large.
Tuesday Nov 19,1996
4-5:30pm
306 Soda Hall
Inferring Sequential Structure
Craig Nevill-Manning
Biochemistry Department
Stanford University
cnevill@cmgm.stanford.edu
http://cmgm.stanford.edu/~cnevill
Abstract:
Structure exists in sequences ranging from human language and music to the genetic information encoded in our DNA. Aspects of this structure can be discovered automatically and made explicit using two recently developed techniques. The first algorithm, Sequitur, identifies hierarchies of repetitions and represents them as a human-readable grammar. A second technique excels at capturing branching and looping structure in the sequence and can be combined with Sequitur to produce a powerful structure inference tool. The talk will introduce the techniques and demonstrate applications to language, music, biological descriptions, program traces, digital libraries and data compression. This work is part of a recently completed doctoral dissertation in computer science, and its application to biochemistry will be investigated during a two year post-doctoral fellowship.
Tuesday Nov 12,1996
4-5:30pm
306 Soda Hall
Edward Large
Department of Computer and Information Science
University of Pennsylvania
Scaling the Dynamical Systems Approach to Path Planning: Competition among Behavioral Constraints
Abstract:
The so-called 'dynamical systems' approach to robot planning and control defines a "dynamics" of robot behavior in which task constraints contribute independently to a nonlinear vector field that governs robot actions. Although this approach exhibits a number of desirable properties, problems arise in scaling to complex behavioral requirements. In this talk, I propose a fast time-scale dynamics that operates in the space of task constraints, determining the relative contribution of each constraint to the behavioral dynamics. The dynamics enforces competition among task constraints and effectively deals with problems that arise when combining constraint contributions. Competitive dynamics makes it is possible to specify behavioral requirements (i.e. tasks) that are more complex than simple navigation. To demonstrate the utility of this approach, I describe the design of a system of two agents that perform a cooperative navigation task. I also show how competition among constraints enables the agents to execute sequences of behaviors that satisfy behavioral requirements. In addition, scalability of the competitive dynamics approach to the design of complex robotic planning systems will be discussed.
Tuesday Nov 5,1996
4-5:30pm
306 Soda Hall
Luca de Alfaro
Department of Computer Science
Stanford University
MODEL-CHECKING RELIABILITY AND PERFORMANCE PROPERTIES OF UNTIMED AND TIMED SYSTEMS
Abstract:
In this talk, we will present methodologies based on temporal logic for the formal specification and verification of probabilistic systems. While in non-probabilistic system the emphasis is on unconditional correctness, in probabilistic systems it becomes possible to study properties such as the likelyhood of incorrect behaviors, and the average performance of a system. Examples of systems that can be studied within this paradigm include software-controlled industrial plants and distributed systems communicating over unreliable channels.In our approach, untimed systems are modeled by finite-state Markov decision processes (MDP), which give a characterization of the system behavior both in terms of probability and nondeterminism. To model timed systems, we introduce probabilistic real-time systems (PRTS), which can specify the probability distribution of transition waiting times, and can also model non-deterministic aspects of the systems. A PRTS can be translated into an MDP by taking advantage of the cost structure associated with the MDP: the cost of the actions will correspond to their temporal duration.
To specify the correctness and reliability of systems, we use the logic pTL*, obtained from the branching-time temporal logic CTL* by adding two operators, P and D: P specifies bounds on the probability of system behaviors; D specifies bounds on the average time between events. In the case of timed systems, the specifications rely also on instrumentation clocks that measure the time elapsed from specified events. We present optimal model-checking algorithms for pTL* specifications for both untimed and timed systems, and we conclude the talk by discussing extensions to the proposed verification framework.
[Top|Home]