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.
@tuankietdang72856 жыл бұрын
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.
@HeinrichChristiansen6 жыл бұрын
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
@brucelee77822 жыл бұрын
@@HeinrichChristiansen I mean what if you just flew a drone above the maze? And connect that drone to the robot through wifi? 😂
@HeinrichChristiansen2 жыл бұрын
@@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.
@apontutul5 жыл бұрын
Thanks a lot. Came here Wondering about Micromouse
@habjuandiego Жыл бұрын
So good! Thanks for the explanation
@camdenparsons51148 жыл бұрын
dynamic programming is actually something else... but you can use dynamic programming to implement flood fill
@samueljimenezavilaАй бұрын
Hi Greetings How do you assign a value to a cell? if the robot is in open space like a living room
@subramaniyanvg63679 жыл бұрын
you are awesome well explained
@nhan15038 жыл бұрын
awrhhhhh!!! Good stuffs... Thank you man!
@mannacharya40887 жыл бұрын
IDK why but the way you put the numbers reminds me of MINESWEEPER LOL
@freetolisten5 жыл бұрын
minesweeper uses flood fill algorithm
@vinaciotm7 жыл бұрын
This method is Awesome, thanks a lot dude!! BR
@muhammadateebaslam5095 Жыл бұрын
How to implement this in arduino? Where is the next video?
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.
@pinkcarots95657 жыл бұрын
THANKYOU!!!!
@AmxCsifier8 жыл бұрын
Genius stuff, subd
@derciferreira2523 Жыл бұрын
Isnt this what backtracking algorithm does?
@gast1287 жыл бұрын
Isn't this just the breadth-first search algorithm?
@jasonzhang26437 жыл бұрын
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)
@AnimilesYT6 жыл бұрын
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.
@ayadjabbar12649 жыл бұрын
thanx allot
@RiteshKasat8 жыл бұрын
nice
@utsavkumar482610 ай бұрын
THiS is not dp, this is BFS in tabulation,
@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
@pc-kn7kt5 жыл бұрын
U easily mark from end but robot do from beginning, confused!?
@NKay085 жыл бұрын
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.
@abdolreza827 ай бұрын
This was pretty useless. If you do t know something why wasting others time?