Transcript AFRL/IF - Department of Computer Science

IISI Overview
Carla P. Gomes
[email protected]
Apr 5, 2006
1
Mission
To perform and stimulate research in
the design and study of
Intelligent Information Systems.
To foster collaborations between
Cornell, AFRL/IF, and the research
community in general,
in Computing and Information
Science.
Scientific
Excellence
Scientific Excellence
Boosting AFRL/IF
research involvement
Boosting
To play a leadership role in the
research and dissemination
of the core areas of the institute.
AFRL/IF
Research
Profile
2
IISI Model
IISI is modeled after successful national research institutes
such as the DIMACS center for Discrete Mathematics and the
Aspen Center for Physics.
• Research collaborations and
projects
• Visiting scientists
• Research conferences and
workshops
• Special research programs
(special periods concentrating
on specific topics and
challenges)
• Technical reports and other
publications
IISI
AFRL/IF
Cornell
Visitors
Outside
Researchers
Research Interactions
3
IISI Scientific Advisory Board
Dr. Robert Constable --- Dean, Faculty of Computing
and Information Sciences, Cornell
Dr. Juris Hartmanis --- Sr. Associate Dean for Computing and Information
Sciences, Cornell
Major Amy Magnus, Ph.D. --- Progr. Manag., AFOSR
Dr. John Bay --- Chief Scientist, AFRL/IF
Ms. Julie Brichacek and Mr. Charles Messenger - Branch Chiefs, AFRL/IF
4
Research Agenda
Design and Study of Intelligent Systems
Quasigroup
Start
Satisfiability
Goal
Planning & Scheduling
(A or B) (D or E or not A)
Data Mining
Autonomous
Agents
Air Tasking Order
Information
Retrieval
Games
Software & Hardware
Verification
Fiber optics routing
Focus:
Computational and Data
Intensive Methods
Automated Reasoning
Modeling Uncertainty
Machine Learning
Information Retrieval
Compute Intensive
Many computational tasks, such as planning,
scheduling, negotiation, can in principle be
reduced to an exploration of a large set of all
possible scenarios.
Try all possible schedules, try all possible plans etc.
Problem: combinatorial explosion!
7
Case complexity
Explosion of number of possible scenarios to consider
1M War Gaming
5M
10301,020
0.5M VLSI
1M Verification
10150,500
100K Military Logistics
450K
106020
20K Chess (20 steps deep)
100K
103010
No. of atoms
On earth
1047
Seconds until heat
death of sun
10K
50K
Deep space mission control
100 Car repair diagnosis
200
1030
100
10K
20K
100K
1M
Variables
Rules (Constraints)
(Kumar/Selman, Darpa IPTO)
Data intensive
What can we store with 1 Terabyte?
Storage
for
$200
video
1 Gigabyte/hour
1000 hours
scanned
images
1 Megabyte each
1 million images
text pages
3300 bytes/page
300 million
pages (Library
of Congress)
Yr ’05, 1 Terabyte for $200.
Wal-Mart customer data: 200 terabyte --- daily data mining for customer trends
Microsoft already working on a PC where nothing is ever deleted.
Personal Google on your PC.
IISI Cornell Researchers
Carlos Ansótegui: Encodings and solvers for combinatorial problems (Computer Science)
Raffaello D'Andrea: Dynamics and Control (Mechanical & Aerospace Engineering)
Claire Cardie: Natural language understanding and machine learning. (Computer Science)
Rich Caruana: Machine learning, data mining and bioinformatics (Computer Science)
JonConrad: Resource economics, environmental economics (Appl. Economics)
Johannes Gehrke: Database systems and data mining. (Computer Science)
Carla Gomes: AI/OR for combinatorial problems and reasoning (Computer Science)
Joseph Halpern: Knowledge representation and uncertainty. (Computer Science)
Juris Hartmanis – Theory of computational complexity. (Computer Science)
John Hopcroft: – Information Capture and Access. (Computer Science)
Thorsten Joachims: Machine learning for information retrieval (Computer Science)
Lillian Lee: Statistical methods for natural language processing (Computer Science)
Bill Lesser: Technology transfer, property rights issues (Appl. Economics)
Keshav Pingali: Intelligent software systems, self-optimizing programs (Computer Science)
Venkat Rao: control theory, planning and scheduling, multi-vehicle systems, AI-controls gap. (Mechanical & Aerospace Engineering)
David Schwartz: Computer Game Design (Computer Science)
Bart Selman: Knowledge representation, complexity, and agents. (Computer Science)
Phoebe Sengers: Human-comp. interaction (Information Science)
David Shmoys: Algorithms for large-scale discrete optimization. (Operations Research)
Chris Shoemaker: Large scale optimization and modeling. (Civil Engineering)
Steve Strogatz: Complex networks in natural and social science (Applied Mathematics)
Willem van Hoeve: CP and OR methods for combinatorial (optimization) problems (Computer Science)
Stephen Wicker: Intelligent wireless information networks. (Electrical Computer Engineering)
Graduate, MEng, and Undergrad students
AFRL/IF Researchers
Across Several Divisons
Boosting
AFRL/IF
Research
Profile
(Curent and past IF researchers/activities )
Andrew Boes – Inductive Logic Programming and reasoning and Reasoning
Joe Carozzoni – Mixed Initiative Planning and Agent Systems
Jerry Dussault – Decision Theory
Nathan Gemelli - Asynchronous Chess
Jeff Hudack - Information Extraction / Knowledge Representation
James Lawton - Agent technology
Jim Nagy - A Peer to peer Databases
Mark Linderman - Modeling Preferences in JBI
Richard Linderman - Architectures and Systems for Cognitive Processing
Robert Paragi - Study and visualization of the effect of structure on problem complexity
Louis Pochet: Active memory systems
Nancy Roberts: Bayesian predictive model of an interactive environment/ AFRL Virtual World
Peter Lamonica: Information retrieval.
Justin Sorice: Games and Reasoninng.
John Spina: Information routing in wireless ad-hoc networks
Matthew Thomas: Dynamic probabilistic target tracking in a distributed sensor network
Robert Wright : Analysis of network vulnerabilities / Asynchronous Chess
11
Mark Zappavigna: Information Extraction / Knowledge Representation
IISI Visitors - Summer
2001/2003/2004/2005
•
•
•
•
•
•
•
•
•
•
•
•
•
Dimitris Achlioptas (Microsoft Research)
Shai Ben-David, (Technion, Israel)
Carmel Domshlak (Ben-Gurion Univ.)
Cesar Fernandez (University of Barcelona)
Eric Horvitz (Microsoft Research)
Joerg Hoffman (Max Plank Inst. )
Henry Kautz (U. Washington)
Leslie Kaebiling (MIT)
Scott Kirkpatrick (IBM/Hebrew University)
Kevin Leyton-Brown (Stanforf Univ.)
Michael Littman (AT&T Research)
Felip Mańa (University of Barcelona)
Fernando Pereira (University of Penn)
Collaborations
With
Outside
Researchers
•Jean-Charles Regin (ILOG/CPLEX)
•Joao Marques-Silva (U. Lisbon)
•Meinolf Sellmann (U. Paderborn)
•Yoav Shoam (Stanford Univ.)
•Cosntantino Tsallis (Physics Center Br
•Manuela Veloso (CMU)
•Toby Walsh (York University,UK)
•Walker White (U. Texas)
•Filip Zelezny (Czech Tech.Un. )
•Wayne Zhang (Un. Washington)
And more…
12
IISI research featured in:
And of course lots of
standard peered reviewed publications…
13
Research Themes
1– Mathematical and Computational Foundations of
Complex Networks
2 – Automated Reasoning: Complexity and Problem
Structure
3 – Autonomous Distributed Agents, Complex Systems,
and Advanced Architectures
14
1 – Mathematical and Computational Foundations of
Complex Networks
Examples
15
The National Academies Study
Network Science
John Hopcroft
(Co-Chair)
•Networks and Network Research in the 21st Century
•Networks and the Military
•The definition and Promise of Network Science
•The content of Network Science
•Status and Challenges of network Science
•Creating Value from Network Science:
Scope and Opportunity
•Conclusions and Recommendations
16
Networks are
pervasive
New Science of Networks
Sub-Category Graph
No Threshold
Utility Patent network
1972-1999
(3 Million patents)
Gomes,Hopcroft,Lesser,Selman
Neural network of the
nematode worm C- elegans
(Strogatz, Watts)
NYS Electric
Power Grid
(Thorp,Strogatz,Watts)
Network of computer scientists
ReferralWeb System
(Kautz and Selman)
Cybercommunities
17
(Automatically
discovered)
Kleinberg et al
Discovering Natural Communities in Large Linked Networks
Proc. National Academy Of Sciences
John Hopcroft, Bart Selman,
Omar Khan and Brian Kulis
Motivation
Huge Data sets,
Readily Available
Black Box/Oracle
(Data Miner)
Results are structured…
Genome Data
… but how well?
The Internet
Data and Results
NEC CiteSeer
Citation graph (no text)
Natural communities –
appear in many
randomized runs
Random Graphs
Hierarchical Structure
CiteSeer Structure compared to
Random Structure
RG1: Same degree structure
NO NATURAL COMMUNITIES
Natural Community Tree
RG2: Adjacency Matrix with
embedded
18 Structure
NATURAL COMMUNITIES?
Impact: Referral Web to Track Nuclear
Scientists in Iraq
19
Research Themes
2 – Automated Reasoning:
Complexity and Problem Structure
Prof. Selman will provide an overview of this area
21
Heavy-tailed Phenomena
in Computational Processes
C. Gomes (Cornell)
B. Selman (Cornell)
Results presented at:
Annual meeting (2005).
Connections and Collaborations
Branching Processes
K. Athreya (Cornell)
Power laws vs. Small-world
Approximations and Randomization
S. Strogatz (Cornell)
T. Walsh (U. New South Wales)
Lucian Leahu (Cornell)
David Shmoys (Cornell)
Random CSP Models
C. Fernandez, M. Valls (U. Lleida)
C. Bessiere (LIRMM-CNRS)
C. Moore (U. New Mexico)
Learning Dynamic
Restart Strategies
HOT:
Robustness vs.
Fragility
Formal Models. Problem
structure, Backdoors
H. Chen (Cornell)
John Hopcroft (Cornell)
Jon Kleinberg (Cornell)
R. Williams (CMU)
John Doyle (Caltech)
Walter Willinger (AT&T Labs) Joerg Hoffman (Max-Planck Inst.)
E. Horvitz (Micrsoft Research)
H. Kautz and Y. Ruan (U. Washington)
Nudelman and Shoham (Stanford)
Information Theory:
22
S. Wicker (Cornell)
Boosting Reasoning Technology Through Randomization, Structure
Discovery, and Hybrid Strategies
Problem Solving Strategies Using
Quantified Boolean Formulas
Encoding problems as Quantified
Boolean Formulas (QBF):
- Objective: generate efficient encodings for QBF
- Idea: keep the cost of detecting local consistency
close to the cost of detecting local inconsistency
Extending state-of-the-art QB Solvers:
- Objective: preserve the natural search space
- Idea: backtrack as soon as an indicator variable
indicates an illegal action.
The problem:
case study: capture black king in k moves
M 0wM 1b  M kw 2M kb1M kwL0  Lk 1
natural search
space
( Ab  ( I  Aw  E w  E b  G))
illegal search
space
• variables
: moves and locations at
:
step i
• axioms
G : Goal
I : initial
Mi, L
position
i
and
effects of White (Black)
A:w , E w ( Ab , E b ) : actions
Does there exist a 1st move for White, such that
for all possible 1st moves for Black, such that
there exists a 2nd move for White, such that
for all possible 2nd moves for Black, such that
…
[the set of logical clauses encoding
“Black king captured” is satisfied.]
Prevent Black to falsify the QBF by performing “illegal”
actions (moves). Ex: “Black moves twice at a step i”.
The solution:
-Objective: given a set of decisions detect, as
soon as possible, the unsatisfiability of the formula,
i.e., the unreachability of the Goal.
Relax (universal quantifier) = existential quantifier
- Idea: in our chess problem, to relax the universal
quantifiers at a certain level forces Black to
cooperate with White at that level. “The
unreachability of the Goal under cooperation
(help mate) is a sufficient condition for the
unreachability of the Goal without cooperation
(regular mate)”
Capture is PSPACE-Complete
Quantified Boolean Formula
global indicator variable
global indicator (z) value ?
Help capture (when all
universals are relaxed) is NPComplete
- Approach: during search, relax subsets of
universal quantifiers (between “capture” and
“help capture”), and check the reachability of
the Goal
Conditional
monitor
QB solver
backtrack if z is up
True or False
The results:
G
Performance of QB solvers
To clausal normal form (CNF) :
Relaxing universal quantifiers:
Non Conditional
instance quaffle
Conditional
semprop
qube
cquaffle
0.01
- Objective: : produce QBF in CNF. Avoid
exponential blown-up in size due to translation
1
3708
0.01
0.01
2
-
*
133
9
3
-
-
-
0.01
- Idea: introduce a hierarchy of auxiliary (indicator)
variables. Indicator variables represent illegal actions
4
-
-
-
0.02
5
-
-
-
0.01
6
-
*
-
9
- Issue: the addition of new indicator variables can
increase the natural search space
7
-
*
*
3.5
8
-
*
*
5.12
9
*
*
*
*
Time (secs): ‘-’ did not
complete in 20,000
seconds;
Carlos Ansotegui
‘*’ formula too large to
execute
Robert Constable
Carla Gomes
Christoph Kreitz
Bart Selman
Problem Solving Strategies Using Quantified
Boolean Formulas
QBF
• New results:
– CNF and DNF formulations for QBF
(submitted to SAT 06)
– Automated generation of so-called Streamlining
constraints
(submitted to AAI06)
24
Operations Research Techniques in Constraint Programming
Willem-Jan van Hoeve
Combinatorial Problems:
logistics, circuit
verification, scheduling, …
solve
solve
solve
Operations Research:
Constraint Programming:
• linear programming
• semi-definite programming
• dedicated algorithms
• exhaustive search
• constraint propagation
(search space reduction)
Combination:
• OR relaxations guide CP search
and prove optimality faster
• dedicated OR algorithms for
fast constraint propagation
Research Themes
3 – Autonomous Distributed Agents, Complex Systems,
and Advanced Archictetures
Examples
26
GDIAC: The Game Design Initiative at Cornell
David Shwartz gdiac.cis.cornell.edu
Research Projects:
► Wargame
development and design
► Game Library
► Curricula
► Outreach
HIERARCHICAL DECOMPOSITION
Raff D Andrea
OBJECTIVE: Develop hierarchy-based tools for designing complex,
multi-asset systems in uncertain and adversarial environments
•System level decomposition
Control of Complex Systems
•Bottom up design
•Model Simplification
•Uncertainty Propagation
•Heuristics and Verification
Relaxation,
Restriction
COMPLEXITY
EXAMPLE: ROBOCUP
DESIRED FINAL POSITIONS AND
VELOCITIES, TIME TO TARGET
STRATEGY
1
PERFORMANCE
DESIRED
VELOCITIES
TRAJECTORY
GENERATION
LOCAL
CONTROL
FEASIBILITY OF REQUESTS
INTERCONNECTED SYSTEMS
•Vehicle platoons
•Finite difference approximations of PDEs
•Cellular automata, artificial life, etc.
•Behavior of groups, swarm intelligence, etc.
DISTRIBUTED ARCHITECTURES:
CHALLENGES:
•LARGE numbers of actuators and zsensorsG
y
•Distributed computation
•Limited connectivity
K
d
u
d(t, s ):
z(t, s ):
y(t, s ):
u(t, s ):
disturbances
errors
sensors
actuators
SEMI-DEFINITE PROGRAMMING APPROACH:
U*
 AY + YA*

C1Y

B1*

YC1*
I
*
D11
B1 
D11  U  0
I 

28
José F. Martínez
Electrical and Computer Engineering
• Reconfigurable chip multiprocessors
– Application-driven dynamic adaptation
• Turn on/off cores
• Fuse/separate cores
• Adjust voltage/frequency
– Multilevel adaptation (HW+SW)
– Applying machine learning (w/ Caruana)
• Learning-based architecture design
• Workshop IISI/IF
– Architectures and Systems for Cognitive Processing
29
Boosting
AFRL/IF
Research
Profile
IISI - AFRL/IF
What can IISI provide
to stimulate research at IF?
• Immersion in an active research environment
• Research advice and infrastructure
• Research Collaborations
• Working group meetings (at IF and Cornell)
• Reading Groups
• Visits by IISI fellows and associates
• Cornell AI seminar and colloquia
• Joint Cornell / IF projects
• Library privileges
• Computer accounts at Cornell
31
• Office space at Cornell
Interactions
Cornell/IF
• Peer to peer collaborations
• Cornell mentoring to IF researchers
– Independent project;
– MSc and PhD co-advising;
– Informal project;
•
•
•
•
•
•
Courses at Cornell (including independent research)
Coordinated research groups at CU and IF
Coordinated research workshops
Collaborative research involving both organizations
Joint projects
Regular Seminars (at IF and CU)
32
Examples of IISI/IF
Collaborations
•
•
•
Multi-Agent Opportunism
Researchs
Paper
Boosting
Jamie Lawton (AFRL/IF-IFED)
Working on
Carmel Domshlak (Cornell) PhD
Project Objective: Develop a model of multi-agent opportunism for
cooperative, heterogeneous agents operating in open, real-world multi-agent
systems
AFRL/IF
Research
Profile
Recognize
Opportunity Cue
Informed of
Opportunity Cue
Opportunity
Cue
Determine
Facilitated Action
– Single-Agent Opportunism: The ability of an individual agent to alter a
pre-planned course of action to pursue a different goal, based upon a
change in the environment or in the agent’s internal state – an
opportunity
Ignore
Opportunity
Other agent ’s
None
Inform
Other Agent
Mine
Decide if Pursuit
is Appropriate
– Multi-Agent Opportunism: The ability of agents operating in a MAS to
assist one another by recognizing potential opportunities for each other’s
goals, and responding by taking some action and/or notifying the
appropriate agent or agents
Approach: Augment existing approaches to single-agent opportunism and
MAS coordination mechanisms with sufficient knowledge-sharing capabilities
to allow agents to recognize and respond to opportunities for one another.
Ignore
Opportunity
No (other
agent)
No (me only)
Yes
Respond to
Opportunity
Negotiate with
Other Agent
Multi-Agent Opportunism Process
Mechanic Agent
• • •
Mechanic Agent
Manual Agent
Benefits:
– Allow the MAS to better adapt to its changing environment by exploiting
History Agent
unexpected events
•
•
•
– Improve in the overall performance of the MAS by allowing agent to
History Agent
complete suspended goals/tasks early (or at all)
– Ensure agents obtain critical information in a timely fashion (i.e.
“Precision-Guided Information”)
Vendor Agent
Middle
Agents
•
•
•
Vendor Agent
Supply Agent
• • •
Supply Agent
Aircraft Maintenance Information System
34
Bayesian Predictive Model of an Interactive
Environment
Nancy Roberts - AFRL/IF,IFED
Carla Gomes Cornell University.
Michael Pittarelli SUNYIT
Objective
Boosting
AFRL/IF
Research
Profile
Master’s
Domain: Office Security
Degree
To apply uncertainty techniques (Bayesian Networks
and Decision Theory) to COTS tools in the area of home
automation and thus, add intelligence to it.
Home Automation - Allows a person to monitor and
control devices(e.g., lights, sensors, cameras, TV’s) in
their own home based on some simple rules.
Problem: To be accurate, you need to model every
situation or else you could get undesired result. (e.g.
Lights turn on or off when you don’t want them to.)
Hardware Used:
3 X10 Sensors,
X10 Tranceiver,
and ActiveHome
X10 CM11A computer
interface
Calculations
 What
is P(BreakIn=Yes |Day=Sunday, Time=830-1700, Sensor=On)?
P(A|B)=P(A,B)/P(B): P(BI|D,T, S) = P(D, T, S, BI)/P(D,T,S)
= P(D=Sun)P(T=830-1700)P(BI=yes|D=Sun, T=830-1700)P(S=On|BI=yes)
i=(yes,no) P(D=Sun)P(T=830-1700)P(BIi |D=Sun, T=830-1700)P(S=On|BIi )
Day
Time
Maximize Expected Utility
BreakIn
“utility(or desirability) X probability”
Sensor
EU(a) = sstates u(a,s)p(s|a)
Software Used:
HomeSeer,
MSBNx, and
Visual Basic
VBscript
X10 Motion Sensor
–
–
–
VBscript
AF Payoff
Provides Improved Accuracy for COTS
S/W
Saves Energy and Money
Other Domains it could be Applied to:
•
•
•
•
Digital Avatars
Agents – Sensor Planning
Interactive Data Wall
Intelligent Intrusion Detection
35
Analysis of Network Vulnerabilities
Cornell / IF Project
Boosting
AFRL/IF
Research
Research
Profile
Paper
Robert Wright (AFRL/IF-IFED)
Meinolf Sellmann (Cornell)
3rd Generation War-Games
 System-on-System
 Model effectiveness of
units wrt current state
within the system
Abstract System as a Network
Identify Points of Failure as
Preferable Targets
36
Impact: Applications
Complexity
in Ad-hoc Wireless Networks
sensor
target
Generalization to Other Ad-hoc Wireless
NetworkProblems
Challenge Problem:
Wireless Target Tracking System
Communicating Doppler radar sensors
tracking multiple targets
The probability of detecting all
targets undergoes a phase transition
with respect to the radar and
communication range.
•
•The computational and
communication complexity
peaks near the phase
transition region.
Communication cost
Radar range
Communication range
Increasing communication range
Detection Probability (%)
Increasing the communication range in an
ad-hoc wireless system increases the density
of the network graph.
•
Radar range
Communication range
Phase transition analysis provides a
mechanism for identifying and
quantifying the critical range of
network resources needed for scalable,
self-configuring, ad-hoc networks
•
Computational cost
Radar range
Communication range
38
Probabilistic Target Tracking with a
Network of Distributed Sensor Agents
Matthew Thomas (AFRL/IF)
Boosting
AFRL/IF
Bhaskar Krishnamachari (Cornell)
Research
Profile
• Project Goals:
– Extend ongoing work on target
tracking using sensor networks
–Distributed sensor network
•limited range, limited communications,
limited power resources
•no centralized control
•how get sensors to work cooperatively in
order to most efficiently track targets?
Model:
–Multi-agent system of sensor network
agents using probabilistic reasoning
– Investigate how the
incorporation of probability
reasoning can reduce energy
consumption by sensors
– Study the communication
costs involved in distributed
decision making with
imperfect information
39
AFRL 3D Virtual World
Nancy Roberts (AFRL-IFED),
Margaret Corbit and Dan White (Cornell),
The objective of this project is to
AFRL Virtual World
explore and apply various artificial
intelligence techniques to enhance a
digital informational environment.
3-D virtual world based on Active Worlds™ used to provide
information about AFRL.
Amphitheatre
Hall of History40
NEW PROJECTS (AFRL/IF-IISI)
•
Asynchronous Chess (AChess) Learning: Learning in a real-time, adversarial, multi-agent
environment. Nathaniel Gemelli, Robert Wright (IFSB)
•
Multi-Agent Sokoban: MAS control and coordination in a computationally complex
logistics domain. James Lawton (IFSB)
•
Automated Reasoning: n-Queens Completion Problem Andrew Boes (IFSB)
•
Efficient Mission-based Information Retrieval Pete Lamonica. (IFED)
•
FLEXDB: An Efficient, Scalable and Secure Peer-to-Peer XML Database. Jim
Nagy. (IFED)
•
Information Extraction; Mark Zappavigna, Jeff Hudack (IFED)
•
Knowledge-based inference. Mark Zappavigna, Jeff Hudack. (IFED)
•
Wargame design, David Ross (IFSB)
•
SimBionic for wargame development. David Ross (IFSB)
•
WARCON (working title) software for Air Academy David Ross, IFSD
41
Nathaniel Gemelli; Robert Wright
Andrew Boes; James Lawton; Jeff Hudack;
AFRL/IF IFSB
Roger Mailler (IISI)
42
Multi-Agent Systems
Multi-Agent Sokoban
James Lawton (AFRL/IF-IFSB )
Single Agent Version
I
Willem van Hoeve (IISI)
Anton Amoroso (IISI)
Bart Selman (IISI)
II
III
43
Multi-Agent Systems
Challenges:
•
•
•
•
adversarial strategies
– selfish agents, restricted resources
– more aggressively: competing teams
cooperative strategies
– collaborating agents, try to achieve
global goal
plan merging
– each agents has own plan, try to
merge and avoid conflicts
coordination
– communication between agents
Real-life applications are often too complex, vague
or biased for general analysis
Multi-Agent Sokoban: structured problem domain, yet
captures all above challenges
44
n-Queens Completion Problem
Andrew Boes (AFRL/IF-IFSB)
Willem van Hoeve and Carla Gomes (IISI)
n-Queens problem: place n queens on an n x n
chessboard such that no queen threatens another
classical AI problem
solvable in polynomial time
applications: parallel memory storage schemes, VLSI
testing, traffic control, deadlock prevention,...
n-Queens completion problem: some queens are preplaced, can we place remaining queens?
unknown complexity, likely to be NP-hard
often very difficult to solve:
?
empty 100 x 100 board takes 0.1 sec
already 1 pre-placed queen may take more than a day!
occurs in practical problems
46
n-Queens Completion Problem
Research goals:
• identify complexity class
• gain insight in problem structure
– phase transition from SAT to UNSAT?
– hardness region?
phase transition
hardness region
time
% SAT
#pre-placed queens
#pre-placed queens
47
n-Queens Completion Problem
Experimental Setup:
•
phase transition:
–
–
•
for given n (100, 200, 500, ...) randomly generate partly
filled board and try to find solution
report % satisfiable boards for each number of pre-placed
queens
hardness region (solution time):
–
for given n (100, 200, 500, ...) report solution time for
each number of pre-placed queens
Hypothesis:
phase transition exists and occurs at the peak in complexity
48
Efficient Mission-based Information Retrieval
Pete LaMonica (AFRL/IF-IFED)
Justin Hart (IISI)
Claire Cardie (IISI)
• Practical Goal: Simplify information retrieval
for analysts in order to improve situational
awareness and simplify analysis
• Real-World Challenge: Analysts do not
necessarily know what they are looking for prior
to finding it. Search queries may not, then,
prove informative
• Approach: Document clustering
49
Efficient Mission-based Information Retrieval
Scatter/Gather
• Browsing documents,
rather than searching
• Software generates
clusters (Scatter)
• User chooses clusters that
they find interesting
• (Gather)
• Software then reclusters
those items that the user
finds interesting
50
Efficient Mission-based Information Retrieval
Research Challenge: In the conclusion of the
Scatter/Gather paper, Cutting et al. state
that the obvious next direction of research
should be to improve cluster quality though
more accurate clustering algorithms
Question: How might Cutting et al. reimplement Scatter/Gather now, almost 15
years later?
Approach
Original paper focused on fast clustering
algorithms, due to hardware limitations.
Replacement of buckshot clustering, used
in original paper, with HAC clustering may
be feasible on modern hardware
51
New Projects
•
Wargame design David Ross (David Schawrtz, IISI)
• SimBionic for AI modeling and implementation in wargame
development.
• WARCON software Air Academy, (David Schawrtz, IISI)
• Information Extraction; Mark Zappavigna, Jeff
Hudack (IFED)
• Knowledge-based inference. Mark Zappavigna, Jeff
Hudack. (IFED)
52
IISI/IF
Tutorials, Seminars, Workshops, Meetings
Tutorial Series I: Constraint Reasoning in Intelligent Systems
IISI Tutorial Series @ AFRL/IF
Willem van Hoeve
Module 1 – Problem domain: logistics: shortest closed route through 13509 cities in USA
(Applegate, Bixby, Chvatal and Cook, 1998)
• logistics, scheduling,
resource allocation,
distributed problems,...
Module 2 - Modeling
• identify key components
• representation
Module 3 - Solving
• search & inference techniques
Module 4 – Application
• COORDINATORs: distributed plan and schedule
management subject to environmental changes
54
Regular Seminar @ IF
with the active participation of
IF and IISI Researchers
(bi-weekly)
IISI – AI seminar
@ Cornell
(weekly)
Workshop 1:
Setting Research Directions in AI:
Knowledge Representation, Discovery, and Integration
Craig Anken
IISI (in collaboration with AFRL/IF), 2003
Workshop 2:
Setting Research Directions in AI:
Mixed Initiative Decision Making
Joe Carizzoni
IISI (in collaboration with AFRL/IF) --- Fall 2003
56
• Workshop 3
Research Directions in Architectures and Systems
for Cognitive Processing
Jose Martinez (Cornell)
Rich Linderman (IF)
IISI (in collaboration with AFRL/IF and CSL) --Summer 2005
57
NESCAI: 1st North East Student Colloquium
on Artificial Intelligence
28-29 April 2006, Ithaca, NY
NESCAI (North-East Student Colloquium on Artificial Intelligence)
Graduate Students Conference
The primary purposes of NESCAI are:
• to foster discussion among graduate students
from the region North-Eastern North America,
• to provide graduate students opportunities to present their work
and get feedback about it,
• to allow networking among the students.
58
Other Resources
Physical Space
New IISI Lab space.
Emphasis on open design.
Space for students, postdocs, and visitors and especially
IF researchers!
60
Conclusions
• IISI --- Benefits to Cornell
–
–
–
–
Opportunity to focus on the core IISI research areas
Develop collaboration relationships
Insights into interesting real world scenarios
Challenge problems and test beds
• IISI --- Benefits to AFRL/IF
– Opportunity to build critical mass in several key research areas
with immersion in an active research environment.
– Develop collaborative research ties with Cornell Researchers.
– Access to Cornell facilities (library privileges, computer accounts,
office space, etc).
IISI provides an opportunity for a close collaboration
between Cornell, IF, and the research community at
large, with a clear potential to further boost the
research profile of both IF and Cornell.
62
U. British Columbia
U. Washington
Microsoft Research
U. Toronto
Stanford
Caltech
U. Texas
U. Cork
Scientific progress by
reaching across
disciplines,
organizations,
and the world.
U. Freiburg
ILOG
U. Pizza
U. Barcelona
U. Lisbon
Hebrew U.
63
Ben-Gurion U.
Computer Science
Engineering
Mathematics
Operations
Research
Economics
Physics
Cognitive Science
Agenda
10:00 - 10:05 Welcome
Prof. Juris Hartmanis, Sr. Associate Dean for CIS
10:05 - 10:35 The Future of Computer Science
Keynote Speaker: Prof. John Hopcroft
10:35 - 11:10 IISI Overview
Prof. Carla Gomes, IISI Director
11:10 - 11:15 Break
11:15 - 11:35 The Next Generation of Automated Reasoning Methods
Prof. Bart Selman
11:35 - 11:55 Research Directions in Architectures and Systems for
Cognitive Processing
Prof. Jose Martinez
11:55 - 12:15 The Game Design Initiative
Prof. David Schwartz
12:15 - 12:30 Discussion
12:30
Lunch
65