Transcript Project Topics: MCI 2007.1

Project Topics: MCI 2007.1
Jacques Robin
Ontologies
Reasoning
Components
Agents
Simulations
Topics Supervised by Prof. Jacques
1. Developing an ontology and component framework of search
algorithms
 Top-level ontology classes derived from Russell & Norvig and Dechter
 Leaves of the ontology:
 to work with a Constraint Handling Rules (CHR)
 to include variations of conflict-directed backjumping for complete global
search
 to include variations of min-conflict for incomplete, local, scalable search
 Using UML knowledge representation and transformation rules from
UML Components to Java OSGi Components
2. Incrementally developing multi-agent simulation
 Starting from simplest simulation of penalty shot
 Using UML as knowledge layer representation language
 Using Java and CHR as implementation layer representation language
Topics Supervised by Prof. Fred
 ??
StateSpaceSearchPb
Framework Top-Level
+fullStateFornulation; Boolean
+suc(State,AgentAction):State
1..*
<<interface>>
StateSpaceSearch
<<component>>
StateSpaceSearch
+gSearch(StateSpaceSearchPb):SearchSolution
+gSearch(StateSpaceSearchPb):SearchSolution
AgentAction
<<uses>>
+name:String
+cost:Real
models
<<uses>>
<<interface>>
ExpandStrategy
<<interface>>
Cost2GoalHeuristic
<<interface>>
PruningHeuristic
+bt(Node):Node
+choose(Fringe):Node
+estimCost2Goal(Node):Real
+prune(Node):Node[*]
<<component>>
BtStrategy
<<component>>
ExpandStrategy
<<component>>
Cost2GoalHeuristic
<<component>>
PruningHeuristic
+bt(Node):Node
+choose(Fringe):Node
+estimCost2Goal(Node):Real
+prune(Node):Node[*]
2..*
parent
child *
Node
+/expanded: Boolean
+/root: Boolean
+/visited: Integer
*
Fringe
NodeSolution
* {ordered}
SearchSolution
Path
PathSolution
+/cost:Real
<<uses>>
<<interface>>
BtStrategy
State
+full:Boolean
+goal:Boolean
+initial:Boolean
<<uses>>
Prof. Jacques’ Search Topic
SearchProblem
PartialStateFormulation
SearchProblem
GlobalSearchAlgo
LocalSearchAlgo
CSPSearchProblem
CSPSearchAlgo
FDCSP
SearchProblem
FDCSP
SearchAlgo
PartialStateFormulation
FDCSPSearchProblem
Backtracking
Heuristic
FullStateFormulation
SearchProblem
VariableChoice
Heuristic
SearchAlgo
FullStateFormulation
FDCSPSearchProblem
ValueChoice
Heuristic
GlobalFDCSP
SearchAlgo
LocalFDCSP
SearchAlgo
CDBJ
Min-Confllict
Tasks
1. Model UML2/OCL2 hierarchy of abstract and concrete specializations of
StateSpaceSearchProblem (2 students)
 including concrete classes and instances of:
 8 queens, CSP backjumping slides map coloring
2. Model UML2/OCL2 hierarchy of abstract and concrete specializations of
CoastToGoalHeuristic (except for CSP problem, fully problem dependent)
(same 2 students than 1)
3. Model UML2/OCL2 hierarchy of abstract and concrete specializations of
ExpandStrategy and PruningHeuristic (Fúlvio)
4. Model UML2/OCL2 hierarchy of abstract and concrete specializations of
BtStrategy (Zé Carlos, Renan)
5. Model UML2/OCL2 hierarchy of abstract and concrete specializations of
StateSpaceSearch as assembly of abstract and concrete specializations
ExpandStrategy, BtStrategy, PruningHeuristic, CoastToGoalHeuristic
(Carlos, Alexandre)
6. Model UML2/OCL2 or other technology search visualization GUI
(Joabe, speak to Luiz Lacerda, [email protected], about his
UML2 Profile for GUI Modeling)
Tasks
1. Implementation OSGi Java, tests JUnit hierarchy of abstract and concrete
specializations of StateSpaceSearchProblem (2 students)
 including concrete classes and instances of:
 8 queens, CSP backjumping slides map coloring
2. Implementation OSGi Java, tests JUnit hierarchy of abstract and concrete
specializations of CoastToGoalHeuristic (except for CSP problem, fully
problem dependent) (same 2 students than 1)
3. Implementation OSGi Java, tests JUnit hierarchy of abstract and concrete
specializations of ExpandStrategy and PruningHeuristic (Fúlvio)
4. Implementation OSGi Java, tests JUnit hierarchy of abstract and concrete
specializations of BtStrategy (Zé Carlos, Renan)
5. Implementation OSGi Java, tests JUnit hierarchy of abstract and concrete
specializations of StateSpaceSearch as assembly of abstract and concrete
specializations ExpandStrategy, BtStrategy, PruningHeuristic,
CoastToGoalHeuristic (Carlos, Alexandre)
6. Implementation OSGi Java, tests JUnit or other technology search
visualization GUI
(Joabe, speak to Luiz Lacerda, [email protected], about his
UML2 Profile for GUI Modeling)
Scope Search Problems
 Priority1:
 FullStateStateFormulation, PartialStateFormulation
 CSPFullStateStateFormulation, CSPPartialStateFormulation
N-queens as FullStateStateFormulation
 N-queens as PartialStateFormulation
 8-queens as FullStateStateFormulation
 8-queens as PartialStateFormulation
 MapColoring as FullStateStateFormulation
 R1-R7 MapColoring as FullStateStateFormulation
 Priority 2:
 PathSolutionProblem
 ShortestPathBetween2Cities
 Romenia
Scope Expand and Pruning Strategies
 General StateSpaceSearch
Priority 1:
 For FullStateFormulationProblems: Depth-first, Backtracking
 For PartialStateFormulationProblems: min-conflict
Priority 2: Uniform cost search, A*
Priority 3: Breadth-first, iterative deepening, RBFS
 CSPSearch:
 Priority 1:
 Variable ordering: Degree Heuristic
 Value ordering: Least Constraining Value
 Pruning: forward checking
 Priority 2:
 Variable ordering: Minimum Remaining Value
 Arc consistency
Scope Backtrack Strategies
 Chronological backtracking
 Conflict-directed backjumping
Time Table
 09-13/07: Version 1.0 of first half of model
 16-20/07: Version 2.0 of first half of model
 30/07-03/08: Version 1.0 of first half implementation and 1.0 of
second half of model
 13/08-17/08: Version 1.1 of first half implementation and 1.0 of
second half implementation and integration tests
 22/08: Final report
Topic 2 Starting Point: Simplest Possible
Multi-Agent Simulation
percept
Shooter
Agent
Simulation
Agent
action
action
Keeper
Agent
percept
gameOver, goal
action(s,legs,shoot(2))
action(k,legs,move(right))
3
2
k
1
s, b
Y
X
1
2
3
2
b
1
s
Y
X
1
2
k
actions(k,legs,move(right))
2
Y
X
2
k
1
s
X
1
2
3
3
2
k, b
1
action(s,legs,shoot(3))
action(k,legs,move(right))
b
Y
3
3
3
3
s
1
2
action(k,hands,grab(yes))
3
k, b
1
Y
X
s
1
2
3
gameOver, nogoal
Topic 2 Possible Task Division
 Simulation Agent:
Reasoning
Simulation Visualization:
Agent Reasoning Explanation Visualization
 Shooter Agent:
Reasoning
Simulation Visualization:
Agent Reasoning Explanation Visualization
 Keeper Agent
Reasoning
Simulation Visualization:
Agent Reasoning Explanation Visualization