Curse-of-Dimensionality-Free Computing, Information-Savvy Controllers and UAV Operations
Abstract
We investigated the use of idempotent (e.g., max-plus) algebraic methods for solution of nonlinear control problems. The main effort used deterministic infinite time-horizon optimal control problems as the vehicle for development of the approach, i.e, we developed the methods for that class of problems as a demonstration of the general approach. We obtained a curse-of-dimensionality-free max-plus numerical method. Combining this new theory with some convex programming based pruning, we demonstrated solution of a particular class on nonlinear problems over six-dimensional space. Standard solution methods would take computational time on the order of decades to solve such a problem, whereas we were able to obtain a solution in under an hour on a desktop machine for the example problem. We also investigated sensing UAV tasking algorithms. We demonstrated that the correct criterion for success, expected reduction of troop losses, took the specific form of a piece-wise linear concave function over a probability simplex. We further found that this class of problems could also be solved efficiently with idempotent methods. This was unexpected, as previously it was believed that one needed idempotent linearity of the associated semigroup for application of such techniques. The key was found to lie in the idempotent distributive property.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 15, 2009
- Accession Number
- ADA573509
Entities
People
- William M. McEneaney
Organizations
- University of California, San Diego