According to Team Project Leader Jeff Conway, artificial intelligence is, basically, search. For the high-school students at the Pennsylvania Governor School of the Sciences, PGSS, their team project on artificial intelligence meant writing a program to find an optimal delivery route given a central depot, trucks, cargo, and customers on a map. In industry and academia, this type of problem is known as the Vehicle Routing Problem (VRP). The PGSS team looked at a particular instance of VRP that also includes time windows (VRPTW), meaning customers are only available for delivery at a certain time. If the trucks arrive before the window, they will have to wait. If they arrive after the customer’s window, the delivery is missed and the solution is invalid. The goal is to minimize the number of trucks, total time, and total distance traveled, while making sure every customer receives cargo and no customers are skipped in the process. VRP is a more difficult version of the traveling salesman problem, while VRPTW is harder still.
How difficult is it to find the best solution to this problem? In the general case, the traveling salesman problem, a computer attempts to find the shortest route for a man traveling to a number of cities where each city is only visited once and he ends back in the city where he started. If there are 60 cities on the map, there are sixty factorial solutions — sixty cities to start in, times fifty-nine cities to go to, times fifty-eight possibilities for the second city…. There are more potential solutions than there are particles in the universe, and to check every solution would take a computer more time than than has ever existed. Problems like this are called “np-hard.” There is a correct solution for the shortest route, but the time to find it is so impossibly large that it bounds the upper limits of computing power.
In order to quickly find the best path for the trucks to follow, the total number of evaluated paths needs to be reduced. For this, the students utilized A* (pronounced “A star”), a computer search algorithm that is especially proficient at path finding and navigating graphs. Some paths are very obviously not the most efficient route, and the computers save time by avoiding those possible solutions. According to team project member Suvir Michandani, A* does this by starting with an initial state and, “generating children states based on variations of the initial state. For each of those children, the children become parents and they have more children. From each of those, the algorithm looks at score and stores those children to find the ones that will lead to an optimum path. It will follow the tree down in order to find a child that is eventually the optimal solution.”
Efficiently modeling the AI world and reducing the time it takes to generate children states are major requirements for solving this problem quickly. What more often defines record breakers is the way their program ranks good paths and bad paths. These heuristic functions choose good and bad decisions based on information in the AI environment or information from the computer programmers. For example, the ‘greedy algorithm heuristic’ always chooses the next-shortest route, even if this discounts longer term strategies that may result in faster pathways. In the students’ project, they had to find a strategy for ranking children states and then decide how many of the ‘good’ states they would continue to evaluate. “It’s not only coming up with clever ways to change the world, but clever ways to proceed through different changes of that world.”
Not only did the students think of clever ways to solve one of these routing problems, at present, the team has tied eight world records in artificial intelligence. For comparison, the current record holders for one of these problems, C201, are two post-doctoral researchers funded by the SMARTRANS Programme of the Research Council of Norway. AI Problems and their record breaking solutions are maintained by the Scandinavian logistics company, SINTEF, who standardizes the problems and evaluates new submissions. In order to maintain equivalence between attempts, each program vying for a record must use the same map, with the same number of customers, with the same time windows, same sized trucks, and same amount of cargo, etc…. The current world record solving for 1200 customers investigates “1.2 billion 3-opt moves in 14 seconds, an average of 12 ns per move.” The solution developed by the high-schoolers of PGSS is absolutely identical to the current proposed solution. Efforts are still underway to further optimize the student solution for this problem, as well as a similar VRPTW with randomized customer maps.
One of the most exciting aspects of the students’ achievement is its availability. The post-doctoral fellows of Norway used a proprietary computing platform that only runs on specialized hardware. These nine students used their personal laptops to code in Python, one of the most widely available, easily adopted programming languages available today. Their solution required the use of two libraries, matplot, to visualize map changes as they occurred, and tkinter for the Graphical User Inferface (GUI). Python and these libraries are free for anyone to download and can be run on virtually any machine. Once the tools were acquired, students discussed how to represent this problem in real-world terms, then defined each process and broke it into manageable pieces for students to code. Once the general structure was working, everyone was invited to come up with clever solutions, trying different things, but also seeing what worked and what didn’t work. One student described the most difficult part of the process was learning to code in a collaborative environment, especially on a team where some members had little to no coding experience beforehand. Version control helped to resolve collaboration problems, while debugging was about as challenging and time consuming as any collaborative project could expect to be. The actual implementation of the code and its concepts was not the limiting factor for these gifted teenagers. Their achievement puts the forefront of computer science research into the hands of anyone with the skill and the will, a forefront that is potentially world-changing and tremendously lucrative.
The reason why this is a benchmark problem, and why it’s studied everywhere, are it’s “massive, massive applications all over the world.” “In addition to the obvious examples like FedEx and UPS, there is Exxon Mobile filling up tankers sending them out. A new example would be Amazon Prime with their delivery drones, which is basically this problem as well. Inside of factories when you have robots that are doing fulfillment they operate basically in a VRPTW.” When one considers the value of transportation, manufacture, raw materials, and the innumerable other industries that can benefit by logistical efficiency, even a slight computational advantage can accrue significant savings. Gains in efficiency reduce the use of fossil fuels and raw material. Fewer road miles means less wear and tear on infrastructure, less pollution from exhaust and wasteful manufacturing processes.
For many Governor’s Schools students, PGSS is their first time to not be the smartest person in the room, their first time asking for help with course work, their first community where everyone appreciates and finds joy in the sciences. This year’s achievement in artificial intelligence comes at an urgent time in the program’s history. Without funding for next year, Pennsylvania’s Governor School for the Sciences will end indefinitely. Originally founded in 1982, the program was temporarily discontinued between 2009 and 2012 due to budget cuts resulting from the 2008 financial crisis. The program was only restored in 2013 due to a massive fundraising campaign by graduates from the program and their family members who founded an educational non-profit. The terms of their bringing back PGSS insisted the program remain 100% tuition free as it had for every previous year of its existence. If a funding source is not found for next summer, sixty of Pennsylvania’s most academically talented students will be without the challenge and community of PGSS. For those interested in learning more about the program and how it can be supported for next year, please visit the Alumni Association website and check out other posts on this blog. There are many avenues of support. Every effort makes a difference for the future of PGSS, for science education in Pennsylvania, and for the amazing students who bring this community to life.