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.
Subscribe to:
Posts (Atom)