Towards effective planning strategies for robots in recycling

[EN]In this work we present several ideas for planning under uncertainty. Our intention is to apply these ideas to recycle electromechanical devices with a robotic arm. This domain presents two challenges: (1) since is not possible to guarantee the desired action outcomes due to limited precision and exogenous factors, the transition model is probabilistic; and (2) it is impossible to know the whole configuration of the device that is being disassembled at once due to occlusions. We opt to formulate the problem as a goal-based MDP (Markov Decision Process) or, equivalently, a SSPP (Stochastic Shortest Path Problem). In general, MDPs’ solutions consist in policies (i.e. a mapping from states to actions) rather than action sequences. Some of the most well-known algorithms to deal with MDPs are Value Iteration and Policy Iteration. However, these algorithms compute full policies and scale badly when the state consists of a large number of variables. Due to the curse of dimensionality, the state space grows too large. In addition, the computational effort invested in obtaining full policies for solving the MDP is wasted when new objects and, consequently, new state variables, are discovered. This renders the previous policy invalid because the specification of the state and the goal changes. Therefore, we explore the effectiveness of an on-line planning method based on determinization followed by classical planning. We take advantage of the well-performing and state-of-the-art systems such as Fast Downward, or the older but still widely used Fast Forward. We consider the following determinization methods, each presenting different strengths and drawbacks: AllOutcome, Single-Outcome, α-Cost-Transition-Likelihood and Hindsight Optimization. Another exploitable feature of our particular domain is that there are strong precedence relations between the components. This allows us to plan hierarchically, bounding the plan horizon and, thus, reducing the computational effort, specially if replanning is necessary. We have hand-crafted a testbed of disassembly problems to test these approaches. In addition, the determinization techniques are tested against domains from past IPPCs (International Probabilistic Planning Competitions ) to see how suitable they are under different circumstances.[CA] En aquest treball presentem diverses idees per planificar sota incertesa. Volem aplicar aquestes idees a reciclar dispositius electromecànics mitjançant un braç robot. Aquest domini presenta dos reptes: (1) no és possible garantir el resultat desitjat de les accions a causa de la precisió limitada del robot i de factors externs i, per tant, el model de transició és probabilístic; i (2) és impossible conèixer la configuració completa del dispositiu que està sent desacoblat degut a les oclusions entre components. Optem per formalitzar el problema com un MDP (Markov Decision Process) amb objectius o, equivalentment, un SSPP (Stochastic Shortest Plan Problem). En general, les solucions dels MDPs consisteixen en polítiques (i.e. funcions que assignen a cada estat l’acció òptima que s’ha d’executar) en lloc de seqüències d’accions. Alguns dels algorismes més coneguts per resoldre MDPs són Value Iteration i Policy Iteration. No obstant això, aquests algorismes computen polítiques completes i la seva complexitat és elevada quan l’estat està format per un elevat nombre de variables. Això és perquè l’espai d’estats és excessivament gran (curse of dimensionality). A més a més, l’esforç computacional invertit en calcular polítiques completes per resoldre el MDP no s’aprofita quan es detecten nous objectes i, per tant, canvia la definició de l’estat i dels objectius, invalidant la política anterior. Així doncs, explorem l’efectivitat d’un mètode en línia de planificació basat en determinització i planificació clàssica. Aprofitem l’eficiència dels planificadore més avançats, com ara Fast Forward. Considerem els següents mètodes de determinització: All-Outcome, Single-Outcome, α-Cost-TransitionLikelihood i Hindsight Optimization. Una altra característica explotada en el nostre domini és que hi ha fortes relacions de precedència entre components. Això ens permet aplicar planificació jeràrquica, acotant l’horitzó de planificació i, per tant, reduint l’esforç de còmput, sobretot si és necessari replanificar. Hem elaborat un conjunt de problemes de desacoblament per evaluar aquestes técniques. A més a més, les tècniques de determinització són provades en dominis de les IPPCs (International Probabilistic Planning Competitions ) de anys anteriors, amb l’objectiu de veure com s’adeqüen a altres aplicacions diferents de la nostra.[ES] En este trabajo presentamos varias ideas para planificar bajo incertidumbre. Queremos aplicar estas ideas a reciclar dispositivos electromecánicos mediante un brazo robot. Este dominio presenta dos desafíos: (1) no es posible garantizar el resultado deseado de las acciones debido a la precisión limitada del robot y a factores externos y, por ende, el modelo de transición es probabilístico; y (2) es imposible conocer la configuración completa del dispositivo que está siendo desensamblado debido a las oclusiones entre componentes. Optamos por formular el problema como un MDP (Markov Decision Process) con objetivos o, equivalentemente, un SSPP (Stochastic Shortest Plan Problem). En general, las soluciones de los MDPs consisten en políticas (i.e. funciones que asignan a cada estado la acción óptima que se ha de ejecutar) en lugar de secuencias de acciones. Algunos de los algoritmos más conocidos para resolver MDPs son Value Iteration y Policy Iteration. Sin embargo, estos algorítmos computan políticas completas y su complejidad es elevada cuando el estado está conformado por un elevado número de variables. Esto se debe a que el espacio de estados es excesivamente grande (curse of dimensionality). Además, el esfuerzo computacional invertido en calcular políticas completas para resolver el MDP no se aprovecha cuando se detectan nuevos objetos y, por consiguiente, cambia la definición del estado y de los objetivos, invalidando la política anterior. Así pues, exploramos la efectividad de un método en línea de planificación basado en determinización y planificación clásica. Aprovechamos la eficiencia de los planificadore más avanzados, tales como Fast Forward. Consideramos los siguientes métodos de determinización: All-Outcome, Single-Outcome, α-CostTransition-Likelihood y Hindsight Optimization. Otra característica explotada en nuestro dominio es que hay fuertes relaciones de precedencia entre componentes. Esto nos permite aplicar planificación jerárquica, acotando el horizonte de planificación y, por tanto, reduciendo el esfuerzo de cómputo, sobre todo si es necesario replanificar. Hemos elaborado un conjunto de problemas de desensamblado para evaluar estos métodos. Además, las técnicas de determinización son probadas en dominios de las IPPCs (International Probabilistic Planning Competitions ) de años anteriores, con el objetivo de ver cómo se adecúan a otras aplicaciones diferentes de la nuestraPeer reviewe