Tim: We have had three strategies: sweeping, sectioning, and the greedy strategy. This week we have divided the boards into which strategy will be best. Do sectioning first, then sweep, then greedy. Also worked on lifecycle. If the first two strategies has finished, then always shift to greedy if there are mosquitos anywhere. The collector is placed very differently depending on the strategy. Lights stop at corners to let the mosquitos catch up. Right now we are simply removing the nodes that are in areas where the walls are too close. For stealing, if the mosquito was lost or stolen on the way out, it would add a lot more time then if it was lost on the way going in.
Franklin: Generate the minimum spanning tree to place the lights and the collector. This is not yet implemented. Looking at weather there is a direct line of sight between sections to prune them.
Vishwa: We fished many of the bugs, like the light being stuck. Also if the A* fails, then the lights turn off and other lights come in and rescue it. When the light is going to get mosquitos, we have implemented code to not steal mosquitos from other lights. Thinking of switching the orientation of the sweeping. Still not able to sweep or section big maze. If you have more lights, the sweep strategy gets much better. In the spiral maze, the stealing was a problem.
Group 2:
Jinesh: The graph generation algorithm will choose a node near the center and them find the nodes around it and then keep spreading out from there. Have the graph dispersal algorithm for the lights is designed so that the lights will get back to the collector at the same time. One we have generated all the nodes to cover all the board with the least overlapping.
Tieram: Our attempts have reduced how well the implementation works. Attempting to build a tree on the board. Get all nodes, then prune them away by line of sight. The pruning algorithm has a problem if there is no nodes in the line of sight, then there could be a section of the graph is disconnected. The problem with the minimum spanning tree, was that we kept getting really long paths, that were minimum spanning tree, but the edges were too long.
Di: The way we are getting our waypoints for each node, then connect each node. Make a waypoint in between the nodes and the obstacles.
Group 3
Harjot: Optimized the collector this week. It is now a function of the board. We place points all over the board. Draw lines from each of these points to each of the waypoints to get a tree. Then use the minimum spanning tree to place the collector at the roots and the lights at the leaves. The placement of the collector will not change depending on the number of lights. We are still going towards the mosquitos, not on the minimum spanning tree. Working on not leaving any mosquitos behind as it is more costly to get them back. The lights take into account the small spaces between the walls. The lights will collect all they can, and they go back. Only using the minimum spanning tree to place the collector and lights.
Tanveer: Light only go into the closed spaces when they are off and then only grab 5 or so mosquitos and then leave to deposit the mosquitos at the collector. Thinking of putting weights on types of distances, like line of sight distances vs. non line of sight distances.
Hao
Group 4
<ran out of time>
Sam
Patrick
Hari
Group 5
Marcus: The strategy of doing the search space is still being worked on. The graph search does a radial search to see if there is a node that can be pruned out. From this graph, we will place the lights evenly spaced from the collector.
Tanay: improved the placement of the collector. Go through the board and creates nodes at 10x10. the collector is placed __. T Lauren: the biggest problem is still the greedy pass. There is still a lot of redundancy on where the lights are going. Big maze works, but there are issues with the weights of the places by the walls.
Group 6
Yigit: We are positioning the collector by first making a grid on the board. if there is an obstacle, not not draw an edge to it. Take a sample of 25 random points on the graph and place the collector at the smallest distance to every other point.
Yang: Place the lights at the leaves. At each check point look for a mosquito that might need a detour and move there. Has fixed Dijkstra implementation to smooth out path. another idea is when all the lights are going back to the collector, thee lights need to go to the farthest mosquito, have the lights go through all the really small openings to get to the mosquito and then go back through the safe path.
| boxes/ lines | Big maze | Satan | |
| 1 | 751 +/- | 321 | |
| 2 | |||
| 3 | 277 | 1217 | 235 |
| 4 | |||
| 5 | 431 | 1664 | 560 |
| 6 | 202 | 918 | 329 |
No comments:
Post a Comment