- Location:
- DC1304
- Time:
- 12:30 PM
- Chair:
- Dan Milgram
1. Adoption of the Agenda - additions or deletions
2. Coffee Hour
- Coffee hour this week:
- Any volunteers?
-
- Coffee hour next week:
- Any volunteers?
3. Next meeting
- Date:
- April 17, 1996
- Location:
- DC 1304
- Time:
- 12:30 PM
- Chair:
- Thomas Pflaum
- Technical presentation:
-
Michael McCool
4. Forthcoming
- Chairs:
-
- Randall Reid
- Navid Sadikali
- Balasingham Balakumaran
- Tech Presenters:
-
- Dan Milgram
- Thomas Pflaum
- Randall Reid
5. Technical Presentation
- Presenter:
-
Steve Mann
- Title:
- Coordinate Free Geometry
- Abstract:
-
-
In this talk, I motivate the use of a geometry abstract data type
to allow for coordinate free calculations and to avoid common
problems that occur when linear algebra is used for geometric
calculations.
6. General Discussion Items
- A reminder that next term we will be having the CGL lab meeting at 1:30 on
Wednesdays, tentatively. Anne needs to book the room, so get back to
her ASAP if you have a conflict.
7. Action List
8. Director's Meeting
9. Seminars
COMPUTER SCIENCE SEMINAR
-Thursday, April 11, 1996
Tuomas Sandholm, Dept. Comp. Sci., Univ. Massachusetts
at Amherst, will speak on ``Negotiation among
Computationally Limited Self-Interested Agents''.
TIME: 11:00 a.m.- 12:00 p.m.
ROOM: DC 1302
ABSTRACT
In multiagent systems, computational agents make
contracts on behalf of the real world parties that they
represent. The significance of such systems is likely
to increase due to the developing communication
infrastructure, the advent of electronic commerce, and
the industrial trend toward outsourcing. My research
normatively analyses such negotiations among agents
that try to maximize payoff without concern for the
global good. The most advanced normative theoretical
tools available are game theoretic. However, in game
theory full rationality of the agents is usually
assumed. My work extends these normative approaches to
settings in which computational limitations restrict
each agent's rationality because combinatorial
complexity precludes enumerating and evaluating all
possible outcomes.
Within the subfield of automated contracting, I
extended the contract net framework to work among
self-interested agents. The original contract net
lacked a formal model for making bidding and awarding
decisions, while in my TRACONET system these decisions
are based on marginal cost calculations. I developed an
iterative scheme for anytime task reallocation where
agents pay each other for handling tasks. I uncovered
and solved problems regarding contracting while old
bids are pending. I constructed three new contract
operators and proved that they are necessary and
sufficient for reaching a globally optimal task
allocation in a finite number of contracts. I also
proved that a leveled commitment contracting protocol
enables contracts that are impossible via classical
full commitment contracts. In addition, it enhances the
efficiency of contracts when full commitment contracts
are possible. Finally, I identified and solved problems
of distributed asynchronous implementation.
Within coalition formation, I developed a normative
theory that states which self-interested
computationally limited agents should form coalitions
and which coalition structures are stable. These
prescriptions depend on the performance profiles of the
agents' problem solving algorithms, and differ
significantly from those for fully rational agents. My
theory includes an application independent domain
classification with bounded rational agents, and
relates it to two traditional domain classifications
with fully rational agents.
Within contract execution, unenforced exchange methods
are desirable among computational agents because
litigation is difficult. I developed such a method
based on splitting the exchange into chunks that are
delivered one at a time. I developed two chunking
algorithms as well as a nontrivial sound and complete
quadratic chunk sequencing algorithm. I also derived
the optimal stable strategies for carrying out the
exchange. Finally, I analyzed the role of real-time and
developed deadline methods that do not themselves
require enforcement.
I evaluated these domain independent methods on an
NP-complete distributed vehicle routing problem with
large-scale instances collected from five real-world
dispatch centers. My methods resulted in significant
transportation cost savings on this problem where
classical game theoretic techniques are inapplicable
due to intractability.
The University of Waterloo
200 University Avenue
Waterloo, Ontario
The Institute for Computer Research (ICR) and the
Department of Systems Design Engineering
Present a Joint Seminar on
"Mining Predictive Patterns from Data: Rough Sets Approach"
by: Dr. Wojciech Ziarko
Abstract:
Data mining is considered to be one of the most promising direc-
tions spanning database and AI research. The primary objective
of database mining methodologies and systems is to help the user
in discovering potentially significant facts or data patterns
which are frequently "buried" in the masses of irrelevant infor-
mation. The patterns of particular interest are associations
between fields in multidimensional data collections. The associ-
ations, once discovered, assume the form of empirical decision,
or prediction rules in the form IF
THEN with the probability P. The rules can be used to
model the development of a complex process, e.g. the reaction of
a stock market to changing external conditions or the reaction of
a biological system to changes in the environment. The rules
derived from data can also be used to control complex processes.
Pattern classification is yet another important application of
the rules. Other data mining problems are analysis of dependen-
cies between variables in multidimensional data and identifica-
tion of fundamental factors affecting such dependencies.
Although statistical methods offer some help in that respect,
their applicability is limited by often strong assumptions and
general lack of techniques to analyze and characterize the struc-
tural relationships existing in data. The analytical methodology
used for data mining presented in this talk is based on the
mathematical theory of rough sets. In the rough sets approach no
assumptions are made about the statistical nature of the data.
The review of rough set-based approach to database mining is the
main subject of this presentation. The presentation will be
developed around an extension of the rough set model, called
variable precision rough sets model. Practical examples computed
with our systems Dataquest, Datalogic and KDD-R will be used to
illustrate the talk. The talk is directed to all individuals
working with data and interested in constructing models from the
data.
The Institute for Computer Research (ICR) and
the Department of Systems Design Engineering
Present a Joint Seminar on
"Learning to Recognize 3-D Objects"
by: Dr. David G. Lowe
of: Department of Computer Science
University of British Columbia
Vancouver, British Columbia
Abstract:
Many potential applications of computer vision depend upon the
ability to recognize objects and track their location over time.
Existing methods for matching 3-D object models to images have
been quite successful for small numbers of rigid objects, but fu-
ture improvements in visual recognition will require methods for
automatically learning models of appearance from images. This
talk will provide an overview of several ways in which statisti-
cal learning methods can improve the reliability and efficiency
of visual recognition. A new learning method called Variable-
kernel Similarity Metric (VSM) learning will be briefly
described.
Date: Friday, April 19, 1996
Time: 3:30 p.m.
Place: William G. Davis Computer Research Centre, Room 1302
10. Lab Cleanup (until 1:30 or 5 minutes)
Meeting Minutes