Group 1:
Yang: Combined the delay and the angle search together. There is no way to get the optimal in a reasonable amount of time, so the code greedily assigns the takeoff and angle. Will look into detecting the impacts on other flights.
Vishwa:
Hari: <excused absence>
Group 2:
Harjot
Tieram: The prioritization influences the order the paths are resulted. So the most problematic flight are resolved first. We have found that this is too simple of a metric and does not work very well.
Sam: worked on identifying and dealing with flows. Did a very similar strategy to group 5, made a wall at the flow and used A* to get around it. The other thing we worked on was prioritizing planes. We first looked at departure time and distance, also at number of intersections (most problematic flights). There was not one strategy that was better then any other. Once the planes are in the air, they don’t change their path.
Group 3
Marcus: Doing a while loop through the planes. Will first see if the plane can get delayed. IF there is a head on collision, we go through the angles to find a good angle for the plane. This is where the infinite loop is.
Hao
Franklin: last week our algorithm was not doing well with many planes. This is because we got stuck in an infinite loop.
Group 4
Tanay: on flow based boards, we need to have the planes go on more of an angle then 10 degrees. Looking at algorithms to find flows.
Yigit <absent>
Tim: We have an array that has all the plane’s location at a round. If we see that there are a lot of planes at the same place in the array, we know that it is a flow.
Group 5
Tanveer: the collision detection is a bit batter then before, it is more general. If there is a crash very near the airport, then the plane departing from the airport will take off on the opposite side. We are not looking at better angles to save on computational time.
Lauren: working on implementing the safety zones. When there are flows on the board, and we are using A*, the A* fails because there is no space to move. We are working on making safe zones to move the planes to if A* fails. We are also working on better collision detection. Previously we were only looking at head on collisions, we are looking at more collisions.
Jinesh
Group 6
Di
Patrick<excused absence>
Future Airplane suggestions
Connecting flights (one to many)
Weather patterns
Change speed
Maximum distance a plane could fly
Add a Z option, so three can be over each other, but 4 is a problem.
No fly zone or Bermuda triangle that randomly changes berring
Thursday, November 21, 2013
Tuesday, November 19, 2013
Airplane 11/14
Group 1:
Yang: Changing plans’ path to go in a curve if there is a crash. There is a trade off between each plane delaying or moving in a curved path. The curved path will take that plane away from the more populated areas. There is no guaranteed that you will get the straight path if you delay.
Vishwa: Tried to optimize performance. Taking into consideration multiple items to prioritize planes. Using the simulation inside the simulation to test if the curve will avoid the crash. On a crowded board it is better to make larger curves to get out of the way. Our approach will not work in a multi-player world, but it should work well in a static world. We only use the angle selection in the beginning before the plane has taken off, nothing gets changed in flight. The flights are evaluated in a certain order, once the plane’s angle is set, all other planes adjust their flight to it. We are not seeing any planes that are taking larger angles. Can optimize the flights to delay more or to have a longer angle. The large angle could lessen the delay, but the plane will be in the air more.
Hari: Look at distance and departure time, to sort planes to change the flight path of.
Group 2:
Harjot: Last time we showed the strategy where the planes will ___. We now look at this as having the obstacle that are moving. Let the plane go in a straight path. Then draw a wall in front of the plane and then uses A*. This is similar to the locking system. After the avoidance we can optimize the delay vs avoid. Does not have something to show yet. Will be plugging in the A* implementation from the mosquito. Will be adding heuristics to avoid having planes moving way out of the way to avoid a crash
Tieram:
Sam:
Group 3
Marcus: We are doing delay first then arcs, which would be better, arch or delay first. Think the end result will be the same.
Hao: if there is a head on crash, then we want the two planes to avoid each other. This has three phases, move to the destination, move away from the other plane, and then move back to the destination. This uses fixed paths. When the simulator detects a crash, find area of the crash and the crash points. When the plane gets to the crash point, move around the crash area and back to the destination. The planes will continue turning after the crash site to get back to its original path.
Franklin: strategy was to only delay. Which works well except for head on collisions.
Group 4
Tanay: Implemented timed delay. If planes are moving towards each other then the implementation is serialized
Yigit:
Tim: working on making a wrinkle in time.
Group 5
Tanveer: Think of the crash point as a junction, and have a time block on that junction. If the angle of crash is greater then 5 degrees, then use delay, otherwise redirect the plane. Will redirect whichever plane is first in the list. Using simulation inside the simulator to check the redirection. Lauren: Changed the strategy, used to have zones around the airport. Decided that the only disadvantage of the delay strategy was the co-linear path. Currently only using delay unless the planes are co-linear.
Jinesh: If the redirection angle is too large then use the delay.
Group 6
Di: The planes start moving at an angle and once it sees its ok to go to the destination, it moves directly there. Thinks it is better to take off and avoid and then to delay.
Patrick: Had trouble with seeing how the plane has gone during A*. Is currently implementing abstractions to see where the plans are at any given time. Flights that departs first and have a long path will be prioritized. Will use Di’s algorithm to move the planes away from the crashes.
Yang: Changing plans’ path to go in a curve if there is a crash. There is a trade off between each plane delaying or moving in a curved path. The curved path will take that plane away from the more populated areas. There is no guaranteed that you will get the straight path if you delay.
Vishwa: Tried to optimize performance. Taking into consideration multiple items to prioritize planes. Using the simulation inside the simulation to test if the curve will avoid the crash. On a crowded board it is better to make larger curves to get out of the way. Our approach will not work in a multi-player world, but it should work well in a static world. We only use the angle selection in the beginning before the plane has taken off, nothing gets changed in flight. The flights are evaluated in a certain order, once the plane’s angle is set, all other planes adjust their flight to it. We are not seeing any planes that are taking larger angles. Can optimize the flights to delay more or to have a longer angle. The large angle could lessen the delay, but the plane will be in the air more.
Hari: Look at distance and departure time, to sort planes to change the flight path of.
Group 2:
Harjot: Last time we showed the strategy where the planes will ___. We now look at this as having the obstacle that are moving. Let the plane go in a straight path. Then draw a wall in front of the plane and then uses A*. This is similar to the locking system. After the avoidance we can optimize the delay vs avoid. Does not have something to show yet. Will be plugging in the A* implementation from the mosquito. Will be adding heuristics to avoid having planes moving way out of the way to avoid a crash
Tieram:
Sam:
Group 3
Marcus: We are doing delay first then arcs, which would be better, arch or delay first. Think the end result will be the same.
Hao: if there is a head on crash, then we want the two planes to avoid each other. This has three phases, move to the destination, move away from the other plane, and then move back to the destination. This uses fixed paths. When the simulator detects a crash, find area of the crash and the crash points. When the plane gets to the crash point, move around the crash area and back to the destination. The planes will continue turning after the crash site to get back to its original path.
Franklin: strategy was to only delay. Which works well except for head on collisions.
Group 4
Tanay: Implemented timed delay. If planes are moving towards each other then the implementation is serialized
Yigit:
Tim: working on making a wrinkle in time.
Group 5
Tanveer: Think of the crash point as a junction, and have a time block on that junction. If the angle of crash is greater then 5 degrees, then use delay, otherwise redirect the plane. Will redirect whichever plane is first in the list. Using simulation inside the simulator to check the redirection. Lauren: Changed the strategy, used to have zones around the airport. Decided that the only disadvantage of the delay strategy was the co-linear path. Currently only using delay unless the planes are co-linear.
Jinesh: If the redirection angle is too large then use the delay.
Group 6
Di: The planes start moving at an angle and once it sees its ok to go to the destination, it moves directly there. Thinks it is better to take off and avoid and then to delay.
Patrick: Had trouble with seeing how the plane has gone during A*. Is currently implementing abstractions to see where the plans are at any given time. Flights that departs first and have a long path will be prioritized. Will use Di’s algorithm to move the planes away from the crashes.
Airplane 11/19
Group 1:
Yang: Trying to assign a curve to each plane in a crash. Will prioritize the flight path and the departure time. This does not always work well since the shorter flights might have to curve more. Previously only looks at the planes about to take off. Now look at each flights based on length no matter the take off time. Tries to get the plane to take off first at an angle before it delays.
Vishwa:
Hari:
Group 2:
Harjot : last time talked about avoidance using A*. Ended up using the simulation. The delay is automatically evaluated since if there is no A* path, then the plane does not take off. When the simulator detects a crash, we create an obstacle box at that point which A* uses to move around. The flights are non deterministic because A* implementation is not deterministic. the bottlenecks are usually at the airports, taking off or landing.
Tieram: There are a lot of cases where taking off another direction and then moving is better then waiting
Sam:
Work on next: prioritization, creating a continuous flow in flow like problems.
Group 3
Marcus: Run the simulation within the simulation that the first two are calculated and the rest are seralized, then calculate the first three then the rest are serialized. We are currently prioritizing the departure time, might have better results prioritizing the arrival time. Not combining delay and arc, either delay plane only or arc only.
Hao:
Franklin: Having runtime issue with more then 15 flights. Still have strategy with delay, if the two planes are heading towards each other, then arc around the plane. If the plane delayed by more then 10, then find an arc that works. This does not actually make much of a difference. Delay first, then after 10 rounds, try and find an angle, if no angle can be found, then delay again.
Group 4
Tanay: If the flights are heading straight into each other, if two flights collide more then 15 times, then the two flights are on a problematic collision. In that case, we will put the two flights on the path and then look 5 steps ahead and greedily move one out of the path, pick the angle that works and gets you towards the destination.
Yigit:
Tim: look at how real air traffic control works. They look at time in air, so we are looking at power. We are preferring straight lines. We sort the straight lines and launch the longest path, and check against the next longest straight line. Will delay the shorter flight. Each plane if given a score of distance and take off time to priority
Group 5
Tanveer: Using the simulation, the primary strategy is the delay, then if there is a head on collision, use simple maths to find the path to narrowly miss it. . Also have the idea of flows, will keep . If there are a number of flights in the air, then seeing the flights as a wall and using A*. Also will change the take off angle if the collision is too close to the airport. To see if there is a flow, keep track of all the flight paths, and if there are more then 5 planes on the same path, then it is a flow.
Lauren:
Jinesh:Use A* to get around the flows on the board.
Group 6
Di:
Patrick: The vast majority of flights are non-conflicting. The trying to implement code to see which is better, delay or curve. Is still looking into using A* and how it might integrate with the other approach.
Yang: Trying to assign a curve to each plane in a crash. Will prioritize the flight path and the departure time. This does not always work well since the shorter flights might have to curve more. Previously only looks at the planes about to take off. Now look at each flights based on length no matter the take off time. Tries to get the plane to take off first at an angle before it delays.
Vishwa:
Hari:
Group 2:
Harjot : last time talked about avoidance using A*. Ended up using the simulation. The delay is automatically evaluated since if there is no A* path, then the plane does not take off. When the simulator detects a crash, we create an obstacle box at that point which A* uses to move around. The flights are non deterministic because A* implementation is not deterministic. the bottlenecks are usually at the airports, taking off or landing.
Tieram: There are a lot of cases where taking off another direction and then moving is better then waiting
Sam:
Work on next: prioritization, creating a continuous flow in flow like problems.
Group 3
Marcus: Run the simulation within the simulation that the first two are calculated and the rest are seralized, then calculate the first three then the rest are serialized. We are currently prioritizing the departure time, might have better results prioritizing the arrival time. Not combining delay and arc, either delay plane only or arc only.
Hao:
Franklin: Having runtime issue with more then 15 flights. Still have strategy with delay, if the two planes are heading towards each other, then arc around the plane. If the plane delayed by more then 10, then find an arc that works. This does not actually make much of a difference. Delay first, then after 10 rounds, try and find an angle, if no angle can be found, then delay again.
Group 4
Tanay: If the flights are heading straight into each other, if two flights collide more then 15 times, then the two flights are on a problematic collision. In that case, we will put the two flights on the path and then look 5 steps ahead and greedily move one out of the path, pick the angle that works and gets you towards the destination.
Yigit:
Tim: look at how real air traffic control works. They look at time in air, so we are looking at power. We are preferring straight lines. We sort the straight lines and launch the longest path, and check against the next longest straight line. Will delay the shorter flight. Each plane if given a score of distance and take off time to priority
Group 5
Tanveer: Using the simulation, the primary strategy is the delay, then if there is a head on collision, use simple maths to find the path to narrowly miss it. . Also have the idea of flows, will keep . If there are a number of flights in the air, then seeing the flights as a wall and using A*. Also will change the take off angle if the collision is too close to the airport. To see if there is a flow, keep track of all the flight paths, and if there are more then 5 planes on the same path, then it is a flow.
Lauren:
Jinesh:Use A* to get around the flows on the board.
Group 6
Di:
Patrick: The vast majority of flights are non-conflicting. The trying to implement code to see which is better, delay or curve. Is still looking into using A* and how it might integrate with the other approach.
Thursday, November 14, 2013
Airplanes 11/12
Group 1:
Yang: You have three options to get from A to B, go straight from A to B, or go on a curve from A to B with a certain radius, or go from A to midpoint c and then back to B. We are using the curve option. The plane starts at a certain angle and checks if there are any crashes. Assigning the path at the time of flight take off.
Vishwa: Observations: We have observed that the lower bound of the best time is as long as the longest flight. Strategy: We will iterate through the list of plane, for each plane we try to find a curved flight path where the curve is a random angle where there are no crashes. We are not currently dynamically moving any plane. We found the plane with the longest distance and that plane will not be changed. Tried to create a priority queue, but had trouble with sorting the bearings. Optimized the player to choose an avoidance angle between -30 and 30.
Hari: Also needed to take into account the departure round.
Group 2:
Harjot:
Tieram: Ran into a problem “pinning” flights that the planes would go parallel to each other. Had two strategies, delay the planes and a dynamic collision avoidance. For the dynamic avoidance strategy, when ever the plans have are too close to each other, they both change their angle away from the on coming plane. The Delay strategy uses math to calculate the delay. If the two planes are heading directly into each other then the avoidance strategy forces the planes to keep turning until they are moving directly away from each other.
Sam:
Group 3
Marcus: Our delay strategy does not work for head on collisions. The departure time delays the flight until the collision has past. The delay gets the closest to the optimal steps. Then look at the planes that have the greatest delay to curve their flight plan.
Hao:
Franklin: Also thinking about using “locks”. We are going to divide the board into 4 x 4 sections, the planes will not take off unless they have all the “locks” to get to their destination. Going to work on figuring out which strategy, delay or avoid is the best to use with the planes.
Group 4
Tanay
Yigit
Tim: also recognized that the lower bound of the best case was the straight line path of the longest flight. Instead of making curves, we delayed the flight. This minimizes the power. We would find the longest flight and “pined” the flight. Does not take into account the departure round. This is also deterministic.
Group 5
Tanveer: Current strategy is to make zones on the boards depending on the airports. If there are multiple flights going to the the same airport, the other planes queue up around the zone. These paths are determines as the planes take off. The planes will not know if they can land until they try to land. We will be trying to optimize the zones to include multiple airports.
Lauren: Thinking about both delay and collision avoidance. Looking at space delay strategy. Worked on finding collision points and then avoiding them. Right now we only look at cashes at the air port.
Jinesh: We are tinkering with the airport zone area.
Group 6
Di: Looking at both delaying and avoidance. Worked on code to make one plane detour and one plane continue straight. No intelligent decision on how to choose which plane gets rerouted and which one goes straight. Always turn the plane to the right.
Patrick: Decided to work on a time dependent A* algorithm. Run the first plane on an A* algorithm. Each node with a plane on it will be weighted really highly. This does not allow a straight line path. This takes care of the situation where two planes are flying towards each other. But this does not take into account the situations where the two flights are departing or arriving at the same destination.
Yang: You have three options to get from A to B, go straight from A to B, or go on a curve from A to B with a certain radius, or go from A to midpoint c and then back to B. We are using the curve option. The plane starts at a certain angle and checks if there are any crashes. Assigning the path at the time of flight take off.
Vishwa: Observations: We have observed that the lower bound of the best time is as long as the longest flight. Strategy: We will iterate through the list of plane, for each plane we try to find a curved flight path where the curve is a random angle where there are no crashes. We are not currently dynamically moving any plane. We found the plane with the longest distance and that plane will not be changed. Tried to create a priority queue, but had trouble with sorting the bearings. Optimized the player to choose an avoidance angle between -30 and 30.
Hari: Also needed to take into account the departure round.
Group 2:
Harjot:
Tieram: Ran into a problem “pinning” flights that the planes would go parallel to each other. Had two strategies, delay the planes and a dynamic collision avoidance. For the dynamic avoidance strategy, when ever the plans have are too close to each other, they both change their angle away from the on coming plane. The Delay strategy uses math to calculate the delay. If the two planes are heading directly into each other then the avoidance strategy forces the planes to keep turning until they are moving directly away from each other.
Sam:
Group 3
Marcus: Our delay strategy does not work for head on collisions. The departure time delays the flight until the collision has past. The delay gets the closest to the optimal steps. Then look at the planes that have the greatest delay to curve their flight plan.
Hao:
Franklin: Also thinking about using “locks”. We are going to divide the board into 4 x 4 sections, the planes will not take off unless they have all the “locks” to get to their destination. Going to work on figuring out which strategy, delay or avoid is the best to use with the planes.
Group 4
Tanay
Yigit
Tim: also recognized that the lower bound of the best case was the straight line path of the longest flight. Instead of making curves, we delayed the flight. This minimizes the power. We would find the longest flight and “pined” the flight. Does not take into account the departure round. This is also deterministic.
Group 5
Tanveer: Current strategy is to make zones on the boards depending on the airports. If there are multiple flights going to the the same airport, the other planes queue up around the zone. These paths are determines as the planes take off. The planes will not know if they can land until they try to land. We will be trying to optimize the zones to include multiple airports.
Lauren: Thinking about both delay and collision avoidance. Looking at space delay strategy. Worked on finding collision points and then avoiding them. Right now we only look at cashes at the air port.
Jinesh: We are tinkering with the airport zone area.
Group 6
Di: Looking at both delaying and avoidance. Worked on code to make one plane detour and one plane continue straight. No intelligent decision on how to choose which plane gets rerouted and which one goes straight. Always turn the plane to the right.
Patrick: Decided to work on a time dependent A* algorithm. Run the first plane on an A* algorithm. Each node with a plane on it will be weighted really highly. This does not allow a straight line path. This takes care of the situation where two planes are flying towards each other. But this does not take into account the situations where the two flights are departing or arriving at the same destination.
Tuesday, October 29, 2013
Mosquito 10/24
Group 1:
Tim: The waypoints are pruned if they are unneeded, if we have uninteresting sections, our pruning function will combine it. We are also looking at the section size. If the size is too big, just going into the section is not enough. If it is too big, now have the lights do a loop around the section. If the number of lights exceed the lights randomly, if not, place them on the sections based on distance from collector. No current code to check if going to the section if beneficial (if there are no mosquitos). On small holes: Need to think about what the purpose is going through the hole, getting to mosquitos? or bringing mosquitos back? On placement of collector: If the lights arrive at the collector a lot before other lights, maybe the collector is not optimally.
Franklin: Have waypoints that are spaced out for the light to got to. The lights will go from the outside and then converge on the collector. Each of the lights move along their waypoints. The collector moves around based on the waypoints. The collector will be in the middle of the graph of the sections. Vishwa is working on the greedy behavior, if a light is already in a section, do not send another light there.
Vishwa <excused absence>
Group 2:
Jinesh:
Tieram: On Approach for small holes: we are ignoring it and also having problems with it. On sweeping: we are having the collector in the corner and have all the lights move towards the collector. Was concerned about the graphs doubling back on itself. Now, generating waypoints around edges, boxing around it to avoid loosing mosquitos. Second idea, how to handle areas in between. Are currently putting waypoints in between boxed in spaces from wall. Are only pruning nodes in wide open spaces, not around obstacles. Need to prune nodes at a corner. Thinking of pruning the waypoints around walls, or disconnect graph and use A* to get around them. Also having problems with small openings. Right now, putting nodes on each side and “hope for the best”. Thinking of adding a weight to make the lights go slower. Thinking of having a very sparse graph, where we will not get all mosquitos on the first path, or have a very comprehensive graph, and not go out. Our pruning strategy is not thinking about how big the light is. Need to adjust the nodes for line of sight from the light.
Di:
Group 3
Harjot: Have not done a lot of big improvements. Added preemptive stopping around the corners. The lights wait at the waypoints. The lights do not go to the targets that other lights are going to. The light are not placed very optimally, same code from the first week, Dividing the board into horizontal regions and places the lights in each section. The collector is placed on a modified minimum spanning tree using A*.
Tanveer: Satan takes a while to load since it is trying to find the best position for the collector based on the A* of all the walls. On Satan’s beard: When the mosquitos are too near the obstacles, the destination is the waypoint and not the mosquito itself
Hao:
Group 4
Sam: Collector is at the middle. It always is. If there is a wall, the program will try and place it as close to the middle as possible. The lights are placed on the corners. The lights are assigned to the sections they are assigned in the beginning, once done, it will go to the closest section. Had trouble getting around the walls, created a buffer and waiting. Now, the lights will pause when moving to get all the mosquitos to come. Problem with implementation is that there are too many sections. Will now, check if there are mosquitos within 5 from light. If not, then the section is marked as finished/claimed, if not, the light will go it it. Lights will abort early (stop sweeping) if it does not need to sweep section. The sweeping motion is predetermined based on the shape of the section. Might have been better if sweep was based on the locations of the mosquitos. Will have a hunter light to go out and get mosquitos that have been missed. The simulator is slow because of the buffer around the walls causing A* to be slow. The sweeping algorithm will start from the left and go down.
Patrick: The lights will pause after 30 movements, for about 5 rounds. This can be tweaked.
Hari: The lights only visit the collector once, after they have swept the sections to avoid duplicate work. The lights would get stuck in the sections because the sweeper was not handling very small sections well. Going forward, adjust the position of the collector.
Group 5
Marcus: Attempted to find the best way to get to through the board through minimum spanning tree. but the graph has too many leaves and is not as good as what we had before. Going to tweak the way to calculate the way to get the path between the nodes. Going to discard the graph, while keeping the the nodes.
Tanay: The collector is placed,
Lauren: Experimented with new approaches, but none were beneficial. Improved the efficiency of A*. Our lights firstly get most of the mosquitos, but then loose some getting back. The greedy is not very good, as it will take a while to get the last few mosquitos.
Group 6
Yigit: <not in class>
Yang: Did not change a lot about the algorithm, but changed the efficiency. Calculate the lie of sight between two points and hash the results. Looking at the small gaps and how the lights go through them. Go through the slightly larger gap, or the slightly smaller gap between the wall the the edge of the board. Determined that going next to the end of the board is the better option. In the cute drawing board, the opening is too small for the lights to see, so the area is invisible, and will only see the mosquitos in to once they leave. In placing the lights, always look at the positions farthest away from the collector
Tim: The waypoints are pruned if they are unneeded, if we have uninteresting sections, our pruning function will combine it. We are also looking at the section size. If the size is too big, just going into the section is not enough. If it is too big, now have the lights do a loop around the section. If the number of lights exceed the lights randomly, if not, place them on the sections based on distance from collector. No current code to check if going to the section if beneficial (if there are no mosquitos). On small holes: Need to think about what the purpose is going through the hole, getting to mosquitos? or bringing mosquitos back? On placement of collector: If the lights arrive at the collector a lot before other lights, maybe the collector is not optimally.
Franklin: Have waypoints that are spaced out for the light to got to. The lights will go from the outside and then converge on the collector. Each of the lights move along their waypoints. The collector moves around based on the waypoints. The collector will be in the middle of the graph of the sections. Vishwa is working on the greedy behavior, if a light is already in a section, do not send another light there.
Vishwa <excused absence>
Group 2:
Jinesh:
Tieram: On Approach for small holes: we are ignoring it and also having problems with it. On sweeping: we are having the collector in the corner and have all the lights move towards the collector. Was concerned about the graphs doubling back on itself. Now, generating waypoints around edges, boxing around it to avoid loosing mosquitos. Second idea, how to handle areas in between. Are currently putting waypoints in between boxed in spaces from wall. Are only pruning nodes in wide open spaces, not around obstacles. Need to prune nodes at a corner. Thinking of pruning the waypoints around walls, or disconnect graph and use A* to get around them. Also having problems with small openings. Right now, putting nodes on each side and “hope for the best”. Thinking of adding a weight to make the lights go slower. Thinking of having a very sparse graph, where we will not get all mosquitos on the first path, or have a very comprehensive graph, and not go out. Our pruning strategy is not thinking about how big the light is. Need to adjust the nodes for line of sight from the light.
Di:
Group 3
Harjot: Have not done a lot of big improvements. Added preemptive stopping around the corners. The lights wait at the waypoints. The lights do not go to the targets that other lights are going to. The light are not placed very optimally, same code from the first week, Dividing the board into horizontal regions and places the lights in each section. The collector is placed on a modified minimum spanning tree using A*.
Tanveer: Satan takes a while to load since it is trying to find the best position for the collector based on the A* of all the walls. On Satan’s beard: When the mosquitos are too near the obstacles, the destination is the waypoint and not the mosquito itself
Hao:
Group 4
Sam: Collector is at the middle. It always is. If there is a wall, the program will try and place it as close to the middle as possible. The lights are placed on the corners. The lights are assigned to the sections they are assigned in the beginning, once done, it will go to the closest section. Had trouble getting around the walls, created a buffer and waiting. Now, the lights will pause when moving to get all the mosquitos to come. Problem with implementation is that there are too many sections. Will now, check if there are mosquitos within 5 from light. If not, then the section is marked as finished/claimed, if not, the light will go it it. Lights will abort early (stop sweeping) if it does not need to sweep section. The sweeping motion is predetermined based on the shape of the section. Might have been better if sweep was based on the locations of the mosquitos. Will have a hunter light to go out and get mosquitos that have been missed. The simulator is slow because of the buffer around the walls causing A* to be slow. The sweeping algorithm will start from the left and go down.
Patrick: The lights will pause after 30 movements, for about 5 rounds. This can be tweaked.
Hari: The lights only visit the collector once, after they have swept the sections to avoid duplicate work. The lights would get stuck in the sections because the sweeper was not handling very small sections well. Going forward, adjust the position of the collector.
Group 5
Marcus: Attempted to find the best way to get to through the board through minimum spanning tree. but the graph has too many leaves and is not as good as what we had before. Going to tweak the way to calculate the way to get the path between the nodes. Going to discard the graph, while keeping the the nodes.
Tanay: The collector is placed,
Lauren: Experimented with new approaches, but none were beneficial. Improved the efficiency of A*. Our lights firstly get most of the mosquitos, but then loose some getting back. The greedy is not very good, as it will take a while to get the last few mosquitos.
Group 6
Yigit: <not in class>
Yang: Did not change a lot about the algorithm, but changed the efficiency. Calculate the lie of sight between two points and hash the results. Looking at the small gaps and how the lights go through them. Go through the slightly larger gap, or the slightly smaller gap between the wall the the edge of the board. Determined that going next to the end of the board is the better option. In the cute drawing board, the opening is too small for the lights to see, so the area is invisible, and will only see the mosquitos in to once they leave. In placing the lights, always look at the positions farthest away from the collector
Thursday, October 24, 2013
Mosquitos 10/22
Group 1:
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.
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 |
Sunday, October 20, 2013
Mosquito 10/17
Group 1:
Tim: The two strategies are good, since some of the boards require a large amount of calculation time in the beginning. Another strategy, make the board into a graph, but prune out all of the obstacles. Divide them up into sections and then make a minimum spanning tree. Use the minimum spanning tree to determine the order of points to visit. Assign the collector at the middle, place the lights at the end and the spaces between the end and the collectors. Need to determine which sections are redundant. Need to add or remove midpoints to the sections depending on the area of the sections.
Franklin: Not currently implemented minimum spanning tree. So, use waypoints instead. Not all of the waypoints are being visited, if they are too close to the wall, they will be skipped.
Vishwa: Our A* implementation fails when the slope is -1. Current strategy, lights start and then continue until it hits a wall, then it goes right and up until it gets around a wall. They have a buffer around the edges of the walls. The lights will go back to the collector, wait there 10 rounds and then switch to the greedy strategy. Lights are placed equidistant on the left side and the collector is in the right size. The lights check that they are not stealing mosquitos from the other lights.
Group 2:
Jinesh: We make a fine grid, start at one point, then look for any nodes in a certain radius, within the radius of the light. Then go to the next one in the line of sight, biased toward the center. Once the lights have made it to the collector, look to see which nodes have not been visited. Working on experimenting with lowest and highest density of mosquitos
Tieram: Need to refactor code. Working on pruning away the leaves of the tree. On the minimum spanning tree, we cases where the diagonal distance is not taken into consideration. Hoping to change the algorithm to start in the center.
Di: In the case of the really small openings, play around with the speed to make sure all of the mosquitos are past the openings.
Group 3
Harjot: have the code that will move the lights around, but not optimize the paths.
Tanveer: Two new things: working on corner cases. Implemented a handoff function for the collector. In small opening case, the lights collect everything outside the box first, then goes to get the next. Creates a new set of waypoints at the openings. Collector is placed on the point closest to the A* points.
Hao
Group 4
Sam: Lights will be placed in the first two sections if there are only two lights. The lights will sweep their section and then go to the next section. Once all the sections have been swept, the lights will go to the collector. Once everything has been claimed, thinking of making another mode to go out and get the final mosquitos. Lights have a start point and an end point of the section to tell the light where to sweep and when it is done.
Patrick: Currently having a bug that is making the light at the collector move back and forth. We need to think about efficient movements between sections. When there are a lot of walls, a catcher strategy might be better then a sweeping strategy.
Hari: fixed bugs in code. paths are determined by A*. Collector is placed in the middle. Planning on placing the collector at most reachable point from all other points. The sections are stored in an array. Have a list of unclaimed sections for the lights to look to go to next. Need to
Group 5
Marcus: New Strategy, trying to formulate the problem as a search optimization of the path the lights are moving. Minimizing the maximum length of the longest path of the light to the collector. Equally space the lights from the collector. Has been having trouble getting the paths equal distance.
Tanay: Check if lights are stuck, then force them out.
Lauren: working on making the lights go along the wall instead of the zig-zag on the board. It works well with the boards with the lights spanning over the board. Still having the issue that if they are not using A*, the lights go too close to the wall and loose mosquitos. A* will take a long time to calculate and freeze the board. Once fixed bug where the lights loose mosquitos, look into not going back to collectors before switching to greedy mode.
Group 6
Yigit:
Yang: Moves the collector at the largest empty space. This makes a sort of random placement.Adding a weight to small openings to discourage lights from going through the openings. The lights stop because they will stay if a movement will result in no longer seeing the mosquito. A light might wait forever if the opening is too small. So, added a time component, that the light will go through the opening if it has been waiting more then 10 rounds.
Tim: The two strategies are good, since some of the boards require a large amount of calculation time in the beginning. Another strategy, make the board into a graph, but prune out all of the obstacles. Divide them up into sections and then make a minimum spanning tree. Use the minimum spanning tree to determine the order of points to visit. Assign the collector at the middle, place the lights at the end and the spaces between the end and the collectors. Need to determine which sections are redundant. Need to add or remove midpoints to the sections depending on the area of the sections.
Franklin: Not currently implemented minimum spanning tree. So, use waypoints instead. Not all of the waypoints are being visited, if they are too close to the wall, they will be skipped.
Vishwa: Our A* implementation fails when the slope is -1. Current strategy, lights start and then continue until it hits a wall, then it goes right and up until it gets around a wall. They have a buffer around the edges of the walls. The lights will go back to the collector, wait there 10 rounds and then switch to the greedy strategy. Lights are placed equidistant on the left side and the collector is in the right size. The lights check that they are not stealing mosquitos from the other lights.
Group 2:
Jinesh: We make a fine grid, start at one point, then look for any nodes in a certain radius, within the radius of the light. Then go to the next one in the line of sight, biased toward the center. Once the lights have made it to the collector, look to see which nodes have not been visited. Working on experimenting with lowest and highest density of mosquitos
Tieram: Need to refactor code. Working on pruning away the leaves of the tree. On the minimum spanning tree, we cases where the diagonal distance is not taken into consideration. Hoping to change the algorithm to start in the center.
Di: In the case of the really small openings, play around with the speed to make sure all of the mosquitos are past the openings.
Group 3
Harjot: have the code that will move the lights around, but not optimize the paths.
Tanveer: Two new things: working on corner cases. Implemented a handoff function for the collector. In small opening case, the lights collect everything outside the box first, then goes to get the next. Creates a new set of waypoints at the openings. Collector is placed on the point closest to the A* points.
Hao
Group 4
Sam: Lights will be placed in the first two sections if there are only two lights. The lights will sweep their section and then go to the next section. Once all the sections have been swept, the lights will go to the collector. Once everything has been claimed, thinking of making another mode to go out and get the final mosquitos. Lights have a start point and an end point of the section to tell the light where to sweep and when it is done.
Patrick: Currently having a bug that is making the light at the collector move back and forth. We need to think about efficient movements between sections. When there are a lot of walls, a catcher strategy might be better then a sweeping strategy.
Hari: fixed bugs in code. paths are determined by A*. Collector is placed in the middle. Planning on placing the collector at most reachable point from all other points. The sections are stored in an array. Have a list of unclaimed sections for the lights to look to go to next. Need to
Group 5
Marcus: New Strategy, trying to formulate the problem as a search optimization of the path the lights are moving. Minimizing the maximum length of the longest path of the light to the collector. Equally space the lights from the collector. Has been having trouble getting the paths equal distance.
Tanay: Check if lights are stuck, then force them out.
Lauren: working on making the lights go along the wall instead of the zig-zag on the board. It works well with the boards with the lights spanning over the board. Still having the issue that if they are not using A*, the lights go too close to the wall and loose mosquitos. A* will take a long time to calculate and freeze the board. Once fixed bug where the lights loose mosquitos, look into not going back to collectors before switching to greedy mode.
Group 6
Yigit:
Yang: Moves the collector at the largest empty space. This makes a sort of random placement.Adding a weight to small openings to discourage lights from going through the openings. The lights stop because they will stay if a movement will result in no longer seeing the mosquito. A light might wait forever if the opening is too small. So, added a time component, that the light will go through the opening if it has been waiting more then 10 rounds.
Subscribe to:
Posts (Atom)