Many applications in scientific computing can be modeled via polynomial systems possibly with parameters. Most information about the initial problem is thus encoded in the solution set of such systems. In the simplest examples, the solutions are a finite set of points, but to model more complex applications, more variables and constraints are needed and the set of solutions can be a curve, a surface or an even higher dimensional object. Some applications, such as robotics or visualization, require a description of the solution set with guarantees. One can distinguish two types of guarantees: topological, all the components and all the singularities (isolated points or self-intersections) must be reported; geometrical, the solution set must be approximated within a given distance. Theoretically, symbolic methods from computer algebra can guarantee the topology of any polynomial system via resultants, Gröbner basis or Cylindrical algebraic decomposition. However, the high complexity of these purely algebraic methods prevents them to be applied in practice on difficult instances. On the other hand, purely numerical methods such as interval arithmetic or subdivision are efficient in practice for non-singular set, but are lacking topological guarantees near singular points. This issue is a long-time challenge in the community of numerical computation. This exposition of the strengths and weaknesses of symbolic/numeric methods advocates for a new trend of work combining symbolic and numeric methods together. The objective of our project is to intertwine further symbolic/numeric approaches to compute efficiently solution sets of polynomial systems with TOPOLOGICAL and geometrical guarantees in the SINGULAR case. Technically, we will explore the use of local algebraic properties (local rings at singularities) and interval arithmetic (Krawczyk operator) to isolate singularities. Currently, certifying the topology around one singular point requires the certification of the topology around all singular points (e.g. homotopy methods) or the usage of non-practical separation bounds (e.g. subdivision). Our new singular certification criteria will be local and will naturally improve algorithms based on subdivision and algorithms based on path tracking. We are aware of the a priori high complexity of the worst-case scenario for general polynomial systems. Hence, instead of working on general systems, one objective is to identify classes of problems with restricted types of singularities and develop dedicated methods that take advantage of the structure of the associated polynomial systems. We focus on two applications: the visualization of algebraic curves and surfaces and the mechanical design of robots. We plan to extend the class of manipulators that can be analyzed, and the class of algebraic curves and surfaces that can be visualized with certification. The partners of the project are selected for the complementarity of their expertises. Guillaume Moroz is an expert of computer algebra and developed the Maple package RootFinding[Parametric] and specific tools for robotics (ANR SIROPA 2007-2011). Marc Pouget is an expert of topology and geometry of curves and surfaces and developed visualization software (CGAL and Isotop). G. Moroz and M. Pouget are both in the INRIA VEGAS team, G. Moroz is new in the team and strengthens the non-linear computational geometry theme of VEGAS. We also have two teams of external collaborators. Joris Van Der Hoven and Grégoire Lecerf are experts in numerical and symbolic computations and computer algebra systems (Mathemagix). Finally, Philippe Wenger and Damien Chablat, from the robotic team at IRCCyN, who work on the mechanical design of manipulators will validate our methods with our prototype implementations.

This project will provide scientific advancements for benchmarking, object recognition, manipulation and human-robot interaction. We focus on sorting a complex, unstructured heap of unknown objects --resembling nuclear waste consisting of a set of broken deformed bodies-- as an instance of an extremely complex manipulation task. The consortium aims at building an end-to-end benchmarking framework, which includes rigorous scientific methodology and experimental tools for application in realistic scenarios. Benchmark scenarios will be developed with off-the-shelf manipulators and grippers, allowing to create an affordable setup that can be easily reproduced both physically and in simulation. We will develop benchmark scenarios with varying complexities, i.e., grasping and pushing irregular objects, grasping selected objects from the heap, identifying all object instances and sorting the objects by placing them into corresponding bins. We will provide scanned CAD models of the objects that can be used for 3D printing in order to recreate our benchmark scenarios. Benchmarks with existing grasp planners and manipulation algorithms will be implemented as baseline controllers that are easily exchangeable using ROS. The ability of robots to fully autonomously handle dense clutters or a heap of unknown objects has been very limited due to challenges in scene understanding, grasping, and decision making. Instead, we will rely on semi-autonomous approaches where a human operator can interact with the system (e.g. using tele-operation but not only) and giving high-level commands to complement the autonomous skill execution. The amount of autonomy of our system will be adapted to the complexity of the situation. We will also benchmark our semi-autonomous task execution with different human operators and quantify the gap to the current SOTA in autonomous manipulation. Building on our semi-autonomous control framework, we will develop a manipulation skill learning system that learns from demonstrations and corrections of the human operator and can therefore learn complex manipulations in a data-efficient manner. To improve object recognition and segmentation in cluttered heaps, we will develop new perception algorithms and investigate interactive perception in order to improve the robot's understanding of the scene in terms of object instances, categories and properties.