Picture for Lydia Kavraki

Lydia Kavraki

Synthesis from Satisficing and Temporal Goals

Add code
May 20, 2022
Suguman Bansal, Lydia Kavraki, Moshe Y. Vardi, Andrew Wells

Figure 1 for Synthesis from Satisficing and Temporal Goals
Figure 2 for Synthesis from Satisficing and Temporal Goals
Figure 3 for Synthesis from Satisficing and Temporal Goals
Figure 4 for Synthesis from Satisficing and Temporal Goals

Reactive synthesis from high-level specifications that combine hard constraints expressed in Linear Temporal Logic LTL with soft constraints expressed by discounted-sum (DS) rewards has applications in planning and reinforcement learning. An existing approach combines techniques from LTL synthesis with optimization for the DS rewards but has failed to yield a sound algorithm. An alternative approach combining LTL synthesis with satisficing DS rewards (rewards that achieve a threshold) is sound and complete for integer discount factors, but, in practice, a fractional discount factor is desired. This work extends the existing satisficing approach, presenting the first sound algorithm for synthesis from LTL and DS rewards with fractional discount factors. The utility of our algorithm is demonstrated on robotic planning domains.

Viaarxiv icon
Github IconAccess Paper or Ask Questions
Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon

Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments

Add code
Nov 27, 2017
Muhayyuddin, Mark Moll, Lydia Kavraki, Jan Rosell

Figure 1 for Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments
Figure 2 for Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments
Figure 3 for Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments
Figure 4 for Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments

Planning motions to grasp an object in cluttered and uncertain environments is a challenging task, particularly when a collision-free trajectory does not exist and objects obstructing the way are required to be carefully grasped and moved out. This paper takes a different approach and proposes to address this problem by using a randomized physics-based motion planner that permits robot-object and object-object interactions. The main idea is to avoid an explicit high-level reasoning of the task by providing the motion planner with a physics engine to evaluate possible complex multi-body dynamical interactions. The approach is able to solve the problem in complex scenarios, also considering uncertainty in the objects pose and in the contact dynamics. The work enhances the state validity checker, the control sampler and the tree exploration strategy of a kinodynamic motion planner called KPIECE. The enhanced algorithm, called p-KPIECE, has been validated in simulation and with real experiments. The results have been compared with an ontological physics-based motion planner and with task and motion planning approaches, resulting in a significant improvement in terms of planning time, success rate and quality of the solution path.

* IEEE Robotics and Automation Letters. Preprin Version. Accepted November, 2017 
Viaarxiv icon
Github IconAccess Paper or Ask Questions
Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon