Planning is a problem in Computer Science with many applications. It can be used to automate robotic tasks or beat players in games, for example. However, it has been very difficult coming up with programs that can approximately plan well. Here, we tackle the problem using a different route. We want to see whether we can improve our ability to approximately plan by using quantum mechanics to model classical systems.
The idea of planning using quantum systems may have some merit. Quantum systems make different assumptions than classical systems so to plan in a quantum system, we have to make a new model. By making a new model and planning on it, we increase the scope of problems we can plan on. Also, there is hope that planning in new quantum models might be simpler than in the classical models, especially when we use a compact basis to plan approximately.
We formulate a new quantum model for planning, give some planning algorithms, and show some experimental results, assuming only elementary knowledge in linear algebra. To formulate a new quantum model and planning, we review discrete quantum mechanics to get an understanding about how quantum systems work. Then, we derive the QuaMDP planning model and show one way to plan in it. We also show one way to generate QuaMDP models from a dynamical system, given its potential energy function. Then, we test how well our algorithms can approximately plan on this new model to find inherent weaknesses and strengths.