Back to search

Georgia Institute of Technology

Task Planning in Factor Graph Representation

Abstract

dc:description.abstract

Many optimization problems in robotics are known to be local, where the problem depends only on a subset of variables (Dellaert 2021). For example, in classical planning, an action chosen between time steps 0 and 1 depends on variables in those time steps, not variables from time step 2. A factor graph is a probabilistic graphical model that has its strength in exploiting the locality property of an optimization problem. Due to this advantage, it is used to model various problems across robotics, such as simultaneous localization and mapping (Dellaert et al. 2017a), structure from motion (Baid et al. 2021), motion planning (Mukadam et al. 2018), etc. Furthermore, the generality of the factor graph enables a unified probabilistic framework, such as simultaneous trajectory estimation and planning (Mukadam et al. 2019). Inspired by this generality, this thesis uses factor graph representation to model classical planning. The classical planning problem represented in a factor graph can be solved using maximum a posterior (MAP) inference, which maximizes the product of all factors in the factor graph. We propose a formulation where the MAP inference will output a series of concurrent actions with the highest probability of reaching the goal state. Classical planning is deterministic, so the probability of reaching a particular state is either True or False. Still, because the proposed method uses a probabilistic graphical model, it can handle probabilistic problems with partial observability and probabilistic success rate of actions. However, MAP inference in discrete space can be computationally intractable because the discrete state spaces grow exponentially with respect to the number of discrete variables. This paper tackles this challenge by utilizing the sparsity of discrete state spaces. For example, most states in classical planning problems would be 0 due to predefined preconditions and effects. The proposed algorithm bypasses states with values of 0s while calculating the maximum a posteriori, significantly improving the computation time for sparse state spaces without any downfall, even in dense state spaces. Finally, the proposed formulation of classical planning with a factor optimized for sparsity is tested on environments where concurrent plans are beneficial. In addition to existing domains for benchmarking, we create a centralized multi-robot environment where concurrent actions can enable shorter horizon plans. Furthermore, the paper discusses the possibility of combining motion planning and classical planning with factor graph representation to create a task and motion planner. The formulation will form a discrete-continuous optimization problem where classical and motion planning problem is interleaved.

Degree

thesis:*
Level thesis:degree_level
Masters
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kim, Yoonwoo
Advisor dc:contributor.advisor
  • Dellaert, Frank
Committee members dc:contributor.committeemember
  • Gombolay, Matthew
  • Xu, Danfei

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/71956

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kim, Yoonwoo. Task Planning in Factor Graph Representation. Masters thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/71956