Table of Contents

1. Introduction to AI and
   Machine Learning (ML)
   • Artificial intelligence
   • Machine learning
   • Deep learning
2. AI and ML Techniques in RCRS
3. AI for Precomputation
   • Path Planning (A*, Dijkstra)
4. ML for Precomputation
   • Clustering (K-Means++)
5. ML for Task Allocation
6. Conclusion

Introduction to AI and
Machine Learning (ML)

Introduction to AI

• The question is: 'What is Artificial Intelligence'?
  

Introduction to AI

• The answer of Russell and Norvig: 'A problem-solving agent'!
  

Illustration courtesy Stuart Russell and Peter Norvig, Artificial Intelligence - a Modern Approach, Pearson.

Types of AI Problems

• Basically... everything robots do!

Terminology

Types of AI Algorithms

Machine Learning

• Subset of AI
• Machine modifies its own algorithm/model/policy/etc. using data
• Human controls the "rules" of how this "learning" occurs, e.g.
  • Choosing a model and its initial state
  • Choosing a learning algorithm
  • Supplying data
  • Enforcing constraints
• Machine applies learning results autonomously on new data/environments/conditions/etc.

Types of ML Problems (and Examples)

• Classification:
  • Binary: Detecting occupancy in a room
  • Multi-class: Detecting the type of animal in an image
• Regression: Predicting housing costs
• Object detection: Locating all pedestrians in an image
• Generation: Computer-generated music from input genre

Types of ML: Unsupervised Learning

• Finding patterns from unlabeled data
• Machine develops its own insights and we have to make sense of them

Types of ML: Supervised Learning

• Determining a model from labeled data
• Goal: Identify labels accurately on new, independent data

Types of ML: Supervised Learning

• Perceptron: The first supervised learning approach
• Use optimization to parameterize a linear classifier
• Other supervised learning approaches extend this with more complex models and learning techniques

Types of ML: Reinforcement Learning

• Technically, a type of supervised learning
• Human provides a mathematical cost/reward function
• Machine repeatedly acts in simulation or real-world trials, evaluates reward, and "learns" to maximize reward over time

Deep Learning

• Not a type of machine learning -- can be unsupervised, supervised, or reinforcement
• Example: "Deep reinforcement learning"
• "Deep" refers to neural networks with many layers
• More layers = more nonlinear = better explains complex systems

AI and ML Techniques in the
RoboCup Rescue Simulation League

Rescue Simulation Challenges

Rescue Simulation Tasks in ADF

AI and ML for Rescue Simulation

• Path planning
  • A*, Dijkstra, depth-first
• Clustering
  • K-Means, K-Medoids, Hierarchical Clustering, Gaussian Mixture Models
• Task Allocation
  • Supervised Learning
    • Classification
    • Regression

AI for Precomputation

• Path Planning (A*, Dijkstra, depth-first)

Path-Planning and Artificial Intelligence

• A problem-solving agent applies a search strategy on the problem:
  
• So, we need a problem formulation (both in Java and MATLAB^®) .

Illustration courtesy Stuart Russell and Peter Norvig, Artificial Intelligence - a Modern Approach, Pearson.

Path-Planning as Graph Search

• Imagine an agent that travels in Romania:
  
• The goal is to get in Bucharest (from Arad).

Illustration courtesy Stuart Russell and Peter Norvig, Artificial Intelligence - a Modern Approach, Pearson.

Path-Planning as Graph Search

• So, imagine an agent that travels on the TestMap:
  
• The goal is to get in [905, 249, 298, 938, 939, 940]
  (from node 976).

Path-Planning as Graph Search

• You not only have to find one solution:
  
• You also have to decide what is the best solution.

Path-Planning as Graph Search

• And you have to find it fast when the map gets bigger:
  
  That is where the search strategy gets important
  (e.g. Dijkstra vs A*)

A* Graph Search

• The Agent Development Framework has an A* implementation:
  
  The problem is solved in 9 steps.

This Java code is provided by Shunki Takami et al.

A* Graph Search

• The steps resembles Uniform-Cost Search:
  
  With a heuristic cost function Path-Cost this is A*
  (with path so-far it is Dijkstra's algorithm).

Illustration courtesy Stuart Russell and Peter Norvig, Artificial Intelligence - a Modern Approach, Pearson.

Multi-Agent decision making

• The actions of the agents are parameterized with the paths.
  
• You need full control and insight in the characteristics of the paths.

Illustration courtesy Mircea Traichioiu, Hierarchical Decision Theoretic Planning for RoboCup Rescue Agent Simulation, Master thesis, University of Amsterdam, 2014.

Export Java data structure to MATLAB^®

Real Java-code

• A little more complex:
  
• This code adds batches. An alternative is to create two complete lists and feed it at once to a MATLAB^®-function.

Effect batch-size

• Adding the nodes to a graph of the Kobe map:

  no batch	15,7999 s
  batch of 25	1,6564 s
  batch of 250	0,6677 s
  batch of 2500	0,42233 s

• For Paris the whole process takes 52,75 s.

Execute this Java-code as precompute process

Load the graph into MATLAB workspace

Visualize Graph

• The (x, y) positions of the nodes are known, but only the edges matter:
   
• That is the connectivity and the distances of the edges.

Plan shortest path

Path found

• There is a clear winner (both in number of steps and distance):
  

Highlight_path is a function of Peter Corke's Robotics toolbox

Find paths faster

• You can use different algorithms to plan a path:
  

shortestpath is modification of Peter Corke's open source Astar implementation.

Modify travel cost after disaster

• After the earthquake building have collapsed and roads are (partly blocked):
  
• In that case the travel costs can be increased:

Blockade illustration is courtesy Ali Modaresi.

Astar will go around blockade

• The edge was not removed, the travel-cost were only increased:
  
• The new path is the red path.
• This can be done for each agent individually, based on observations and team-communication.

ML for Precomputation

• Clustering (K-Means++)

Clustering

• Finding patterns from unlabeled data
• Basically, clustering is the task of dividing data points into a number of groups
  • data points in the same group more similar to each other than to those in other groups

Clustering

• Finding patterns from unlabeled data
• Generally, clustering is the task of dividing data points into a number of groups
  • data points in the same group more similar to each other than to those in other groups

How is clustering useful to Rescue Agent Simulation?

Clustering for
Agent Simulation

• Teams use clustering during precomputation mostly for
  • partition the map by grouping buildings and roads based on their location (x, y)

Commonly, Partition Clustering Methods are used, such as K-Means++ or K-Medoid

Clustering for Agent Simulation

• Teams could also use clustering to group buildings based on their propensity to fire ignition inferred from properties like
  • floors
  • totalArea
  • fieryness
  • temperature
• Gaussian Mixture Models (GMM) may provide better results
• However, the clustering method
  • maybe too complex to develop and maintain, or
  • there is a need to compare different methods

MATLAB^® Clustering

• MATLAB^® provides several clustering algorithms:
  • K-Means (Lloyd, 1982)
  • K-Medoids (Kaufman & Rousseeuw, 1987)
  • Hierarchical Clustering (Kaufman & Rousseeuw, 2008)
  • Gaussian Mixture Models (Marin et al., 2005)
  • Hidden Markov Models (Baum & Petrie, 1966)

Generate Data

Execute Java-code to generate data

Import Data

MATLAB^® Processing

Call MATLAB^® from Java

Connect to MATLAB^®

• Start a MATLAB^®
  MatlabEngine ml = MatlabEngine.startMatlab();
• Connect to a shared MATLAB^®
  if ( MatlabEngine.findMatlab().length > 0 ) {
   MatlabEngine ml = MatlabEngine.connectMatlab();
}
  
  • Requires an instance of MATLAB^® open
  • Session shared
    matlab.engine.shareEngine

Call MATLAB^®

• Evaluate an expression
  [output1,...,outputN] = eval(expression)
  Example:
  ml.eval('cd tutorial;')
  
• Evaluate a function
  [y1,...,yN] = feval(fun,x1,...,xM)
  Example:
  Object[] mlOutput = ml.feval( 2, "kmeans", (Object) mlInput, 10, DISTANCE, 'cityblock', MAX_ITER, 100 );

Clustering Performance

ML for Task Allocation

• Methodology for Target Selection

ML for Task Allocation

• MATLAB^® can help optimize rescue operations by predicting more accurately certain future state
• Example
  Ambulance teams can optimize their rescue operations by predicting more accurately the chance of potential victims to survive.

Methodology

1. Generate data
2. Import data into MATLAB^®
3. Train model in MATLAB^®
4. Integrate into ADF
5. Refine the target selection model

Generate Data

Execute Java-code to generate data

Import Data into MATLAB^®

Categorize Data

Train model in MATLAB^®

• Supervised machine learning methods can be applied to learn associations between observable variables and hidden variables (part of a causal model of the world).
• Estimates of the value of variables of a world model can be done with
  • discrete states (classification)
  • continuous states (regression)

Train model in MATLAB^®

• We use the MATLAB^® Classification Learner app to train a model to predict the chance victims have to survive based on an estimate of the remaining health points (HP) at the end of the scenario simulation.

Classification Learner

Classification Learner

• Classification
  • Feature Selection
  • Principal Component Analysis (PCA)
  • Model Type
  • Parallel Execution
• Plots
• Export Model - Export Compact Model

Validation

• The training and validation steps compose an iterative process whose cycle should be repeated until the validation accuracy is satisfactory.

Integrate into ADF

Integrate into ADF

• The function can then be called inside the calc method of the HumanDetector class for the ambulance team agents

Target Allocation Strategies

• Ambulance team can combine the classification information with several other information about victims to determine which one to rescue
• Possible policies are
  1. classify all known victims
  2. discard the predicted dead, and
  3. select
     1. random victim among them
     2. the closest victim
     3. the closest victim that is predicted Critical

Conclusions

• Problem solving
  • Path-planning (Astar, Dijkstra)
• Unsupervised learning:
  • Classification (k-means clustering of city blocks)
• Supervised learning:
  • Classification (k-nearest neighbour prediction of victim class)
  • Regression (bagged tree model of remaining HP of victim)

Future Works

• Assess different strategies for task allocation
• Compare different clustering algorithms
• Use JNI to access MATLAB® libraries
• Evaluate the feasibility of implementing a Rescue team in MATLAB®

Thanks