Robot Platform Motion Planning using Answer Set Programming.
Julian J. Portillo, Carmen Leticia García-Mata, Pedro Rafael Márquez-Gutiérrez, Rogelio Enrique Baray-Arana · 2011
Abstract. We discuss how a path planning problem for a robotic platform was solved modeling it with the axioms of the action language AL and described in Answer Set Programming, ASP. The environment of the autonomous vehicle is static. A set of dynamic, static and inertial laws are used to describe the vehicle domain. The optimum solution is chosen using two criteria: minimum distance and minimum obstacles dodged required to arrive to the goal. One advantage in using ASP for planning problems is related with its complexity. In case of classical planning problems it is known they are PSPACE-complete for finite domains and undecidable in the general case. By fixing the plan length, the planning problem is reduced to NP-complete. Since Answer Set Programming is a totally declarative language, the problem solution relies in the ASP’s solver, which is NP-space, as it has been already proved elsewhere. Consequently, for solvable problems, the solutions are always found.