Publication

A tutorial on the use of graph coloring for some problems in robotics

Dominique de Werra, Tinaz Ekim
2009
Journal Articles

Abstract

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the location of the Entry/Exit station where the robot unloads the collected items after each trip along the corridor. The links of these systems with generalized coloring problems and other applications such that train shunting and pallet loading problems are discussed and related results are obtained. We conclude with several open questions on the topic. (C) 2007 Elsevier B.V. All rights reserved.

Official source

https://infoscience.epfl.ch/entities/publication/d88a6d9b-fac7-4cdf-a542-b87d7bd75be2

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Dominique de Werra, Tinaz Ekim
2009
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/d88a6d9b-fac7-4cdf-a542-b87d7bd75be2

About this result

Related concepts (31)

Robot

A robot is a machine—especially one programmable by a computer—capable of carrying out a complex series of actions automatically. A robot can be guided by an external control device, or the control may be embedded within. Robots may be constructed to evoke human form, but most robots are task-performing machines, designed with an emphasis on stark functionality, rather than expressive aesthetics.

Robotics

Robotics is an interdisciplinary branch of electronics and communication, computer science and engineering. Robotics involves the design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist humans. Robotics integrates fields of mechanical engineering, electrical engineering, information engineering, mechatronics engineering, electronics, biomedical engineering, computer engineering, control systems engineering, software engineering, mathematics, etc.

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Related publications (32)

A tutorial on the use of graph coloring for some problems in robotics

Chat with Graph Search

Exact Obstacle Avoidance for Robots in Complex and Dynamic Environments Using Local Modulation

Hitting with Different Joints of a Robotic Manipulator

Online Multicontact Receding Horizon Planning via Value Function Approximation