Speech Transcript - COOPERATIVE PREY HERDING BASED ON DIFFUSION ADAPTATION

0:00:13	oh to more late
0:00:14	that kind of behaviour in other works
0:00:16	we have used a diffusion adaptation to model for example
0:00:21	a flight formations symbols
0:00:23	to models warming of be is moving from one place to another
0:00:28	to uh to model bacteria more to two we had then the a people in this conference on a in
0:00:32	how but T search for four
0:00:34	or hell fish just want to go that is of four
0:00:38	to move to the than insertion of food so these are all examples of highly dynamic environments with the agents
0:00:43	some moving the topology of the network is changing of time
0:00:47	your neighbours are changing all the time
0:00:49	okay
0:00:50	so
0:00:50	nodes need to do adaptation in all the to learn
0:00:54	what's happening at on them and all that also to says what the neighbours think about the situation
0:00:59	okay
0:01:00	so before i start let me just evade be talk to day i'm going to show a video of it's
0:01:05	not my you to download it from the internet
0:01:07	and this a figure illustrates the behavior that i'm going to model today use see
0:01:14	and a a a group of fish lots of fish being
0:01:17	right
0:01:18	uh followed by a a group of shot
0:01:21	now
0:01:21	i'm going to model of is as two separate networks called in a thing we've each other be sharks form
0:01:26	a network of nodes to are in eighteen with each other
0:01:29	and the purpose is to encircle
0:01:32	a a group of fish and the fish is on the network of feature
0:01:35	that are call the meeting with each other and the purpose is to try to get away way and also
0:01:39	find before for done go dollars
0:01:41	before the locations of these are two separate networks
0:01:44	they have their on an object is but at the same time
0:01:47	they have
0:01:48	some form of a competitive interaction between each other okay so that we show you this C behaviour in in
0:01:54	nature of forced you see here it is
0:01:58	you see how we we shocks is a fish
0:02:01	and then they are back them one at a time that's have they
0:02:04	and they a function
0:02:06	okay so that it is they all have a code in a of this some not shocks the thing this
0:02:10	the all phones
0:02:11	no okay so
0:02:13	if five
0:02:14	you want to see if again
0:02:16	so that's what they do okay
0:02:18	that's how they
0:02:20	they play for four days circle circle the fish and then they are dark at one at a time okay
0:02:24	case of course this is this
0:02:26	a small example the
0:02:27	but i i'm sure that
0:02:29	there are more
0:02:30	complex examples in nature are okay so now let's come back to the math okay to new method
0:02:36	and to that modeling i'm going to do
0:02:42	to model that kind of behave and i'm going to use a call diffusion adaptation algorithms
0:02:46	so that we force motive the algorithms for you
0:02:49	by and that's what i need and that's for that consists of a collection of notes these nodes have a
0:02:54	adaptation and learning abilities select me motivated for us assume you have a collection of and know
0:02:59	that collected to each other through neighbourhoods circuits so you have a topology and this topology can change with time
0:03:05	because "'cause" and going to use it for the application
0:03:07	at hand
0:03:08	and that's assume
0:03:09	i'm not going to both
0:03:11	in the case the movie the deviations and the arguments of come just going to highlight the main ideas is
0:03:15	friend interested in the details the references
0:03:18	well help you with that of kid just because but i don't have time here to go through all the
0:03:21	deviations
0:03:23	but i going to highlight the main ideas
0:03:26	we set of nodes they have a model objective and that object of for example is that you all effect
0:03:31	of W O
0:03:32	this this down real all could the present the location of for all of them would like to know what
0:03:36	the food is
0:03:37	or it would represent the location of the are all of them would like to know with the shock is
0:03:41	an avoid it right
0:03:43	so a so you have a collection of a with the common object and each node each node
0:03:49	has an index K each node has access to some measurements
0:03:52	but related to that the objective for example each node
0:03:55	can sense it distance
0:03:57	do that objective and noisy distance and is noise
0:04:01	and can also sense in what that action that the object of its i know the distance and i of
0:04:05	the direction but all of this is up to now
0:04:08	okay okay because you are innovative noisy environment then each node in the network has access to that kind of
0:04:13	information
0:04:14	now how do they work together so that the local or the nation of from local cooperation they can improve
0:04:21	the estimate of word
0:04:22	V four days or of where the but a is all
0:04:25	improve the estimate of what have a parameter the network is trying to estimate a cam just using
0:04:30	the fish as an example in this context okay
0:04:33	and now you can formulate a global optimisation problem like this which says
0:04:38	a i have and nodes
0:04:39	all these nodes would like to find a weight vector
0:04:42	data you or the location of what that were for them looking for in order to minimize the sum of
0:04:47	the squares
0:04:48	okay this could be one cost function K
0:04:50	of course this is a global optimisation problem and we don't want to solve
0:04:54	it in a global man and we would like to solve it in a distributed manner okay because
0:04:59	every node K only has access to information coming from its in egypt neighbours okay so how do for that
0:05:05	problem in a distributed manner and we have started this problem in late data several publications only earlier
0:05:10	and we motivate the algorithms and we started its performance convergence performance times and performance is that is the performance
0:05:17	okay so he i'm just summarising the algorithm and all the set and done
0:05:21	this is one of the algorithms that you have one
0:05:25	that performs very very well okay and why i mean these algorithms we also insisted on coming up with a
0:05:31	good things that are simple to implement
0:05:33	because i believe that in applications like we one i'm showing you hear and i'd these agents i'm not very
0:05:39	sophisticated bill might be able to be implementing very complex
0:05:42	algorithm so we would like to see if you can him late
0:05:45	these kinds of complex behaviour through simple procedure is okay so this is one of the algorithms we have i
0:05:51	call it the at the diffusion fusion algorithm had that then combine "'cause" it consists of two steps
0:05:57	okay okay each node note K the first think it does it starts with an estimate of for that
0:06:03	that's see think of it as the location of the predator or four
0:06:07	a first think it does it uses a a measurements it has for example it's S estimate of the this
0:06:12	that's and the direction
0:06:14	it uses that
0:06:15	information to try to improve one its current estimate
0:06:18	that we give it an improved in to need to estimate and then it costs also with its neighbours it
0:06:23	combines
0:06:24	for the convex combination here the estimates from its neighbours
0:06:28	two and up with it improved estimates so this is a two-step procedure
0:06:32	the D there's of the must not math methods don't matter what matters is the process the process is
0:06:37	you know
0:06:38	for example
0:06:40	this is a very different from consensus type solutions in consensus step solutions if a it's just if you are
0:06:45	a way if a are familiar with that
0:06:47	you try to
0:06:49	a you require a agents to reach consensus about some something to agree
0:06:54	i something a kiss all over that each each node is essentially a averaging the information from its neighbours
0:07:00	in these kind of applications that they showed you the example that i showed you you can not to require
0:07:05	you you should not expect be nodes to reach consensus
0:07:08	because the fish that's closest to the shot should behave in a different manner than the fish that's as to
0:07:13	the for don't far away from the shore
0:07:15	you have to allow for individual that's estimate of the situation as well
0:07:19	so that's why
0:07:20	these diffusion algorithms algorithms always consist of two steps one of them is con thought and with the neighbours let
0:07:26	me see what the neighbours think about with four days
0:07:29	but before i take that for granted that also want to says it from my perspective
0:07:33	okay
0:07:34	uh uh where the shark is a with before is
0:07:36	relative to me so you always have personal assessment
0:07:40	okay a local processing local adaptation and learning in addition to
0:07:45	collaboration with your neighbours okay so this is always there okay you always have these two steps
0:07:50	and this is called adapt then combine adaptation comes before combination you also have combined then at that
0:07:55	and you have several different variations of these algorithms this one works very well okay
0:08:00	and these coefficients they always add up to one
0:08:03	over the neighbours on these graph they are just a last what i just
0:08:06	yeah explain okay
0:08:08	now in nature there are many many examples of source stick kate organise behaviour that are right
0:08:14	okay from local interactions between you node you in one is the the fish
0:08:18	behave like it's forming this very but for geometric figure
0:08:22	right
0:08:23	but is not sense brain telling them sitting here on this side and telling and you position yourself at this
0:08:29	particular location right
0:08:30	this is happening this is the result of highly localised processing okay
0:08:34	the diffusion adaptation algorithm i showed you is one example of high localised processing because every node is only coordinating
0:08:41	with that in you jet neighbours
0:08:43	you also have this kind of behaviour of the fish
0:08:45	but i D S to of the boats fine in V formation i again that is more central
0:08:50	bad board telling them sitting on the side and telling them this is what you okay to cells okay so
0:08:55	these are examples of highly complex
0:08:57	so self organized behavior that the result from local processing at the local level look
0:09:03	so the algorithm i just described to you the diffusion algorithm that i described use one example of
0:09:08	localise processing that leads to this kind of behaviour in and i'm going to illustrate it do you to
0:09:14	but showing you how
0:09:15	this algorithm can in more the behaviour of sharks all for putting on face
0:09:21	in the case when you have two networks competing against each other right and trying to get the out that
0:09:25	and the other trying to get away from
0:09:27	from the forced okay
0:09:29	is so now
0:09:30	uh uh uh
0:09:31	so
0:09:33	oh this is known that for example here this kind of behaviour is known and uh in a at if
0:09:37	you have let's say the shock yet trying but are a group of fish that have force in moving together
0:09:43	in harmony the ford and then start the me a shot peers
0:09:47	now the fish is known to behave in this manner they have this found and effect behaviour at they turn
0:09:52	around
0:09:52	they do not on
0:09:54	okay and can almost a long this and shots so they turn around and come back from behind
0:09:59	okay so they are known to behave in that manner so about going to model
0:10:03	that behaviour so that you
0:10:05	okay and then he are also i shall video the we do that i show here you see it in
0:10:10	a different man that here you have the collection
0:10:13	a sharp sold bill things and you have some fish she and you see the end up in so
0:10:17	if a fish and then they start at back them one at a time but to side
0:10:21	and in the video "'cause" this are just illustrations from the which are this is from the I B B
0:10:25	ball you to the and other kind sent this and the this we goes from scientific american and this it
0:10:30	is it's from some other
0:10:31	or or go shown down
0:10:33	and down here a can now again like i said before don't to much about the math okay because we
0:10:38	don't have time to go through the D as but let me explain in high level
0:10:41	a big use the algorithm i should do before that's all you need to to in more like that kind
0:10:45	of behaviour
0:10:47	okay
0:10:47	i to think about that like this okay you have a group of fish they don't know where the four
0:10:52	days so that's one object objective they have an mind i need to find with the four days
0:10:56	they can use the diffusion adaptation algorithm to estimate where the location of before this is to local cooperation number
0:11:02	one
0:11:03	no but to they also need to stay away at i'm where
0:11:05	the shot are
0:11:07	right so they have a that estimation problem that they need to solve a need to know where the shocks
0:11:11	are
0:11:12	so you have to
0:11:13	diffusion adaptation process is that they need to do and right in a distributed manner
0:11:18	the sharks they need to know where the group of fish is so they need to track for example with
0:11:23	the centre of gravity of a group of fish is
0:11:26	uh uh that estimation problem i they can also use a themselves the diffusion adaptation algorithm of the form i
0:11:32	showed you to estimate with the centre of gravity of the
0:11:35	group of fish is and track at that i'd because they need to follow that
0:11:38	and this so open so you can see that at the core of solving this problem you have to fall
0:11:43	for the or four
0:11:45	estimation problems all of them distributed estimation problems each one of them can be solved exactly in the same and
0:11:51	that okay so you see the uniformity here so one of these things is to try to show that with
0:11:56	this thing classifier algorithms with this same type of processing you can in one eight different kinds of behaviour
0:12:01	know because if you think about it this is something very very interesting
0:12:05	you see you you with think that to to model the uh the a flight formation in boards of the
0:12:09	the way but to a move you would need different kinds of algorithms and models those for each scenario and
0:12:16	interesting thing is with this same general kind of a with them they want a should do before you kind
0:12:20	of produce these different kinds of behaviour
0:12:22	okay
0:12:23	so here what you have just a a a a high level description you can divide the region at i
0:12:28	around the shark to for regions
0:12:31	region and one up here use the up here each in one
0:12:33	if if if is is region one T to means he's far away from the shot okay you defined this
0:12:38	C is in terms of a at I if it's away from the shock if you stay if you just
0:12:42	want to use
0:12:43	tracking where the for this and continues moving was before
0:12:46	no okay that's what it means
0:12:47	if if if fish finds itself so if if fish find itself
0:12:57	more
0:13:03	if a fish finds itself in region two
0:13:06	which means he's calls to or okay
0:13:08	then what you would do a double take it own i perpendicular to the direction of motion of the shot
0:13:13	so that's why he also needs to track where the shark is okay
0:13:16	so i'm telling you how they we use the information they get from the estimation process okay they
0:13:21	i get this information to do something with it they have to a decision with it's so well this fish
0:13:26	is tracking from local cooperation with the other fish with the shark is
0:13:30	if they that out they are to close to the shock that one move along a direction they would take
0:13:34	get to a like a should before the found in effect
0:13:37	they won't take a turn perpendicular to that that action this is what this not they me okay
0:13:42	if they are for example to to close to be we and one hundred eighty degree turn and move away
0:13:47	a okay
0:13:47	so essentially what this at is thing and what these conditions are telling you is how the fish use the
0:13:52	information they get from the solution of the distributed estimation problem okay they use it to evaluate how close they
0:13:58	are to a shock and then what decision they should make should they move
0:14:02	one you moving to the for should they
0:14:04	for all the found an effect well should they divorce and move back that that's actually what it means okay
0:14:10	and what that means is they are going to set their velocity vector that how long this uh and direction
0:14:14	of P
0:14:14	so the result of the estimation process affect how they said the velocity vector or okay
0:14:20	now
0:14:21	after the fish set but it like used for in the found an effect beta group with fish usually group
0:14:26	work "'cause" a how do they re group okay again
0:14:29	what they do is eight that for example and this step but it they become separate networks and that's what's
0:14:33	nice about that now you have set but at network
0:14:36	so one can say the out
0:14:38	okay i so one of them for example of this network can find which
0:14:42	one is which i if that is a net will close to it and which fish she's cost to it
0:14:46	and move in that direction so that they group
0:14:49	okay
0:14:50	so these sub networks can also track each other through local cooperation
0:14:54	and then take an action in the uh i i i uh uh
0:14:57	i um
0:15:00	a the act to that and move or or other subnet will give this one a we these sub networks
0:15:05	to group okay
0:15:09	so sing
0:15:12	yeah this fall all week is not working well here it's
0:15:15	chomping thing over several slides that
0:15:17	ones
0:15:18	the is
0:15:28	and a let me show the yeah as this we you before i come to you this is the case
0:15:31	of K using the kind of a bit they should you hit it is you have a group of fish
0:15:35	trying to find a for would okay it will be and then a shot at
0:15:39	so you can think that the fish they don't know what the for is they are called than eighteen to
0:15:43	find with the four days and moving in that direction but there was a of for the shot is
0:15:48	and the track it and then use see the found an effect and they group one on in you
0:15:52	continue their right you see so a this is all to produce with a kind of a with them i
0:15:57	showed you
0:15:57	however in this example i only have one network the fish networks so it's only the fish that's doing diffusion
0:16:02	adaptation
0:16:03	the problem i discussing today i'm showing to the case where you have to a networks a group of shocks
0:16:08	and facial case i'm going to show you that very so on
0:16:11	so what do they shot to do what do this shot do with the result of the estimation process with
0:16:15	a is out of tracking well the centre of gravity of a group of fish a
0:16:19	well where the closest fish is to sam what do they do with the result of that distributed estimation problem
0:16:24	the shocks they have a
0:16:26	several decisions to make
0:16:27	okay i'm not going to go again for all the mathematics but they have several say it's one of them
0:16:31	is chase if the fish just to a way they decide
0:16:34	that's just move towards the centre of gravity of that group
0:16:37	so they are tracking the centre of gravity that they set of the lost a vector do that that actually
0:16:41	are okay
0:16:43	once they get calls to it within a certain date as they decide to is or call it so they
0:16:47	move not a the attention or K they move along that that it's of that is to what the fish
0:16:52	were building but okay
0:16:53	so once they get close with it's or and they just they say a let me now is so call
0:16:57	it okay let's nice is it and and one at that time they take to are
0:17:02	you like that wide leans in and so the fish case so essentially they have a state machine that they
0:17:07	fall
0:17:09	and based on based on the estimation of sell the use the they transition from one state to another depending
0:17:15	on how close they are to the centre of mass okay so this is just a producing
0:17:20	in figures and equations what i just explained in plain in plain walls okay so i'm not going to both
0:17:25	a all of these the there's of course that is
0:17:27	and that is small in that will not that behaviour so if if the shock as far away he just
0:17:31	keeps moving towers the centre of gravity
0:17:34	okay once to gets that he starts so
0:17:36	that group
0:17:38	can and not only that if if fish moves for that i they would like to keep the fish within
0:17:42	a circle of the fish of one of them moves away from the so they will track that vision bring
0:17:46	came back okay
0:17:47	so all of that
0:17:49	so all of that requires that you use the distributed estimation problem okay i'm i don't have much time to
0:17:55	both a the uh sort of these small in but you are that to get an idea i would like
0:17:58	to show you
0:17:59	no i would like to show you V uh defined assimilation simulation than at break for
0:18:03	here you see this example now you have to network
0:18:06	right
0:18:06	you see how the shots since so fish
0:18:09	okay
0:18:11	let me let you watch it and then and makes some comments
0:18:14	you see and then they at that one at that time
0:18:17	okay now think about this to you see this is an example of a highly dynamic network okay and that
0:18:23	network that's moving all the time
0:18:25	your neighbour are changing all the time feelings of bit topologies changing all the time
0:18:30	number one number two each one of these networks you have to networks each one of them has an objective
0:18:35	the fish wants to find a way before it's
0:18:38	but it the estimation process
0:18:40	what do for exactly for that's would would be moving as well
0:18:43	the shocks would like to know what the centre of gravity of the fish and want to track that and
0:18:47	in tap that
0:18:48	and also the fish would like to avoid the sharks okay
0:18:51	so you have several object is okay in a high dynamic environment and a highly caught productive
0:18:57	and competitive environment like and you end up with a high and and a network that's able to adapt and
0:19:03	learn
0:19:03	a in real time okay so this is
0:19:06	an example of adaptation at the higher level and learning at a high level and then usual and you can
0:19:11	see just simply using that diffusion algorithm that i expect you before you are able to reproduce the be here
0:19:16	that i showed do before uh in the video and a lot a like to the other the real example
0:19:20	of how shocked friends
0:19:22	i go off to fisher okay
0:19:24	and you i hope i conveyed the main idea okay of of this kind of behaviour i again this is
0:19:29	all signal processing what you're saying here
0:19:31	all generated using
0:19:33	a diffusion adaptation algorithm i showed you before and using the result of the distributed estimation process to make decisions
0:19:39	should they move closer or should i so oh that's essential the kind of the decisions you make a okay
0:19:44	so and we this of some reference if you are interested in more to learn more about this some going
0:19:48	to stop S so that we stay on time okay so if you have any quick questions
0:19:52	before i move on to the second part yes please
0:20:03	i
0:20:04	yes
0:20:09	they don't have a job from the for the uh
0:20:13	so okay in any of the like take advantage of the behavior have your of other one of knowing that
0:20:18	be have your of other one to to maximise its proof
0:20:21	a i okay in this in this particular the model that i have here the information that's shared between the
0:20:26	network is the positions of the centre of gravity of the large network and the position of the there's in
0:20:32	this small a network so they know essentially a deep but they don't know this strategy that the other group
0:20:38	is falling they just know where the locations are and they spun
0:20:41	according to be process you that explain you before T that you move away well you D for or you
0:20:46	take an i two degrees is uh okay so that's the this strategy to they use in this particular example
0:20:51	okay
0:20:52	now if they knew exactly what strategy each other group or i would assume that you got but have to
0:20:57	do better yeah that's a good question but that we haven't done that
0:21:01	okay yes
0:21:05	i
0:21:06	a yes okay right that's a very good question of course C M just showing a very uh uh the
0:21:11	networks behaving but then you need to study the steady-state behavior of these kinds of networks the converge and we
0:21:17	have done that and other walks okay we have shown we have a derived expressions for the mean squared error
0:21:22	in steady-state state okay
0:21:24	how how close they get to the location of if we have done that in previous works yeah
0:21:29	of course for small step-size a the step size have to be small amount
0:21:32	for them to converge
0:21:35	oh can maybe one more question just so that we stay on time yes
0:21:38	here you assume that the sharks for example have the same state machine in each of them right let's say
0:21:43	for example there are different groups of sharks right which like to like if an state machines very but but
0:21:49	i is a tight so
0:21:51	is
0:21:51	right which might apps
0:21:53	behaving hating using a different types of machines as i a good question we haven't done that but you know
0:21:58	this are all generalisations that are possible to pursue so okay yeah and and and see what kind of behave
0:22:03	that emerges from that kind of of assumption what you thing about the real life i mean i R D's
0:22:09	i mean it's state machines are
0:22:11	well already very uh i mean somehow
0:22:14	or the or already in the sharks or or yeah that i think we have to ask an animal behaviour
0:22:19	expert okay yeah all we all yeah or they are knowing okay we'll it would it some of the lead
0:22:24	to channel and they explain about
0:22:26	be thinking process that these animals both through these state machines and are trying to see if you can to
0:22:30	produce that kind of behaviour
0:22:32	using the signal processing algorithms and models that we have a okay but this are all good questions okay but
0:22:37	to and so then you have to get deeper into a right to how and most be uh you know
0:22:41	i want to be fit to the other because i don't want okay maybe we should move one i would
0:22:45	be glad to talk to you i your questions after this session okay sorry for that just because they have
0:22:50	to move on to the second

COOPERATIVE PREY HERDING BASED ON DIFFUSION ADAPTATION

Distributed and Collaborative Signal Processing

Presented by: Ali H. Sayed, Author(s): Sheng-Yuan Tu, Ali H. Sayed, University of California Los Angeles, United States