Dynamic Programming / Flood Fill Algorithm

For the rest of the videos in this course, go to learn.akrobotn... and login as a guest.

[@HeinrichChristiansen]

Hi there This algorithm is only good when the robot "knows" the target destination position. In real life it is a different case. The Robot knows only what it can "see" in real life and does not know the distance, nor does it know the destination position.

[@tuankietdang7285]

What is your solution to this problem? I'm making a maze solving robot and I'm working to figure out how to solve this problem.

[@HeinrichChristiansen]

Hello Tuan I guess it depends on what exactly you want it to do: 1: Do actual mapping by trying all possible directions that have not yet been tried, until it reaches the target point, which will be the (as far as I know) only true way to do it. There are other videos that demonstrate this. 2: Let the target emit some kind of beacon which the robot then can measure the distance to which is what this video is actually illustrates in the way of finding the path, but this demands knowledge of where the Target position is located. Something similar to echo location. 3: The view above the maze which in itself may be considered to be cheating. That however might be the quickest way to find the way through a maze to any target points, as it reveals to the robot the maze structure, before even making the first move. Model 1 is the absolute true way to map a maze to a target point, as you don't have any information except from what you remember having not been explored already or having been explored already so you know you don't need to re-explore. Model 2 is Semi-true as sometimes if you yourself get lost in a maze can yell out for help being a beacon, which will make the search somewhat easier. Model 3 is like having an already prepared map in your hand, it is more or less like using a GPS. I guess this answer may be useful to you and possibly others too. Regards Heinrich

[@brucelee7782]

@@HeinrichChristiansen I mean what if you just flew a drone above the maze? And connect that drone to the robot through wifi? 😂

[@HeinrichChristiansen]

@@brucelee7782 The suggestion is good, and still, maybe not. It does not have a connected counterpart or does it? What if it's an underground maze?!? Then a Drone wouldf not be any good anyway.

[@elazarpimentel5340]

I guess many people will end up here after Veritasium's video on Micromouse. This was my question the whole time, they don't mention it in the video, but you can tell the robot knows that there are x,y cels and the goal is in 45,76 or whatever. Other than making just left turns and turning on another corner if you do a loop, I would love to know what other algorithms are there to find the target. That might be another category of Micromouse.

[@camdenparsons5114]

dynamic programming is actually something else... but you can use dynamic programming to implement flood fill

[@muhammadateebaslam5095]

How to implement this in arduino? Where is the next video?

[@mannacharya4088]

IDK why but the way you put the numbers reminds me of MINESWEEPER LOL

[@freetolisten]

minesweeper uses flood fill algorithm

[@apontutul]

Thanks a lot. Came here Wondering about Micromouse

[@subramaniyanvg6367]

you are awesome well explained

[@abdolreza82]

This was pretty useless. If you do t know something why wasting others time?

[@nhan1503]

awrhhhhh!!! Good stuffs... Thank you man!

[@utsavkumar4826]

THiS is not dp, this is BFS in tabulation,

[@gast128]

Isn't this just the breadth-first search algorithm?

[@jasonzhang2643]

I think so. The trick is to apply BFS starting from the destination so that you know what is the distance between each node to the destination. You can also apply BFS from the starting position but you need to find the path backward (from destination back to the starting position)

[@AnimilesYT]

Breadth first search does it slightly different. It creates a path as it goes along, but it doesn't go to nodes it has already visited in another path. This gives the path with the shortest amount of nodes.

[@Electromaniaworld]

very nice.... thanks

[@derciferreira2523]

Isnt this what backtracking algorithm does?

[@habjuandiego]

So good! Thanks for the explanation

[@peaceforwhat7681]

Start with the target cell??? Im so confused

[@lukeqiao5477]

how do u program this?

[@saritadevi5213]

kzbin.info/www/bejne/nJa9lpxve6l1oNUsi=vj7d3MKeJszkRcJQ

[@hecticfn6368]

Isn’t this just like the A* search algorithm, I don’t really understand the difference between this algorithm and A*. If anyone knows the difference, I’d appreciate it if you told me it.

[@fluidiccolours8091]

You can imagine this flood-filling algorithm a simpler version of A* search algorithm. Now take an A* search algorithm and do these three steps: 1. Start the algorithm from the destination to the start. (Instead of start to destination in A*) 2. Set the heuristic cost function to zero. 3. Instead of picking one cell at a time with the least cost in the A*'s open-set, prioritize all the cells in the open set. If you do all these three, then A* becomes a floodfill. The reason being, A* uses the heuristic function and costs to narrow the search window. So, A* will not search the entire grid/maze by default unless otherwise the situation demand. However, the cost computations are costly. Since the algorithm has to pick only one cell in the open-set at a time, it has to compare the costs of all the cells in the open-set and pick one with the least cost. This search will take a lot of time especially if the open set has too many entries in it. Not to mention it takes a lot of memory as well. Flood fill on the other had has a tendency to fill the entire grid/maze. Because of the lack of a heuristic function, the algorithm traverses the entire grid/maze by default and picks a narrow path only when the situation demands. Because of the lack of heuristic function, the cost computations are cheap. Since there is no priority cue to pick a candidate cell like A*, all the cells in the open-set can be used without comparison and this is much faster. However, there is a downside - memory fluctuations. A*'s heuristic function and priority cue prevents a huge number of cells to be added to the open-set at any given time and discarded at any given time. So, A* algorithm doesn't have massive memory fluctuations. However, Floodfill will have massive memory fluctuations.

[@vinaciotm]

This method is Awesome, thanks a lot dude!! BR

[@Aysimlisa]

How to code this?

[@aliphulazam1590]

excellent

[@rembrandtes]

good video nice explanation again

[@ayadjabbar1264]

thanx allot

[@RiteshKasat]

nice

[@rembrandtes]

good , well explained ......

[@AmxCsifier]

Genius stuff, subd

[@user-sdhndhfmfc]

thanks for the explanation

[@timog7358]

great video

[@petercohen3966]

What software are you using?

[@pinkcarots9565]

THANKYOU!!!!

[@pc-kn7kt]

U easily mark from end but robot do from beginning, confused!?

[@NKay08]

This doesn't matter, as you already know the map and the starting position and goal. All you want to find is a path to the goal.

[@balorprice]

Good explanation! One correction, that's not a flood fill but the A* Pathfinding algorithm. It's the best algorithm you could use to solve a problem of this nature