Transcript cellular presentation

1
Vision based Motion Planning using Cellular
Neural Network
Iraji & Bagheri
Supervisor: Dr. Bagheri
Chua and Yang-CNN








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 Introduced 1988.
 Image Processing
 Multi-disciplinary:
–
–
–
–
Robotic
Biological vision
Image and video signal processing
Generation of static and dynamic patterns:
 Chua & Yang-CNN is widely used due to
– Versatility versus simplicity.
– Easiness of implementation.
Sharif University of Techology
2
Network Topology








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 Regular grid , i.e. matrix, of
cells.
 In the 2-dimensional case:
– Each cell corresponds to a pixel in the
image.
– A Cell is identified by its position in
the grid.
 Local connectivity.
– Direct interaction among adjacent
cells.
– Propagation effect -> Global
interaction.
C(I , J)
Sharif University of Techology
3
r - Neighborhood








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 The set of cells within a certain distance r to
cell C(i,j). where r >=0.
 Denoted Nr(i,j).
 Neighborhood size is (2r+1)x(2r+1)
Sharif University of Techology
4
The Basic Cell








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 Cell C(i,j) is a dynamical system
– The state evolves according to prescribed state equation.
 Standard Isolated Cell: contribution of state and input
variables is given by using weighting coefficients:
Sharif University of Techology
5
Space Invariance








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 Inner cells.
– same circuit elements and element values
– has (2r+1)^2 neighbors
– Space invariance.
 Boundary cells.
Inner Cells
Boundary Cells
Sharif University of Techology
6
State Equation








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 xij is the state of cell Cij.
 I is an independent bias constant.
 yij(t) = f(xij(t)), where f can be any
convenient non-linear function.
 The matrices A(.) and B(.) are known as
cloning templates.
 constant external input uij.
Sharif University of Techology
7
Templates








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 The functionality of the CNN array can be
controlled by the cloning template A, B, I
 Where A and B are (2r+1) x (2r+1) real
matrices
 I is a scalar number in two dimensional cellular
neural networks.
Sharif University of Techology
8
Block diagram of one cell








Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
 The first-order non-linear differential equation
defining the dynamics of a cellular neural network
Sharif University of Techology
9
ROBOT PATH PLANNING USING
CNN









Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
Path Planning
By CNN
 Environment with obstacles must be divided into
discrete images.
 Representing the workspace in the form of an M×N
cells.
 Having the value of the pixel in the interval [-1,1].
 Binary image, that represent obstacle and target and
start positions.
Sharif University of Techology
10
Flowchart of Motion Planning










Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
Path Planning
By CNN
Flowchart of
Planning
CNN Computing
Sharif University of Techology
11
Distance Evaluation











Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
Path Planning
By CNN
Flowchart of
Planning
Distance
Evaluation
 Distance evaluation between free points from the
workspace and the target point.
– Using the template explore.tem
– a is a nonlinear function, and depends on the
difference yij-ykl.
Sharif University of Techology
12
SUCCESSIVE COMPARISONS METHOD












Introduction
Network
Topology
r-Neighborhood
The Basic Cell
Space
Invariance
State Equation
Templates
Block Diagram
Path Planning
By CNN
Flowchart of
Planning
Distance
Evaluation
Successive
Comparison
 Path planning method
through successive
comparisons.
 Smallest neighbor cell
from eight possible
directions N, S, E, V,
SE, NE, NV, SV, is
chosen.
 Template from the
shift.tem family
Sharif University of Techology
13
Motion Planning Methods






Basic concepts
Proposed
Model (FAPF)
Local Minima
Stochastic
Learning
Automata
Adaptive
planning system
(AFAPF)
Conclusions
 Global Approaches
Decomposition
Road-Map
Retraction Methods
Require a preprocessing stage (a graph structure
of the connectivity of the robot’s free space)
 Local Approaches: Need heuristics, e. g. the
estimation of local gradients in a potential field
 Randomized Approaches
 Genetic Algorithms
Sharif University of Techology
14