Grid Coloring for Object Sensing and Localization (Master's Internship)

The Inria Saclay-Île-de-France Research Centre was established in 2008. It has developed as part of the Saclay site in partnership with Paris-Saclay University and with the Institut Polytechnique de Paris .

The centre has 39 project teams , 27 of which operate jointly with Paris-Saclay University and the Institut Polytechnique de Paris; Its activities occupy over 600 people, scientists and research and innovation support staff, including 44 different nationalities.

Within the framework of a partnership with Nokia Bell Labs.

Starting time: Position available at any point before june 2025 (duration: up to 6 months).

Internship Supervisors:

• Cedric Adjih, Research Scientist
  Department/Lab: INRIA, TRiBE team, Saclay, France
  https://www.inria.fr/en/tribe, Contact: cedric.adjih@inria.fr
• Chung Shue (Calvin) Chen, Research Scientist
  Department/Lab: Nokia Bell Labs, ML & System team, Paris-Saclay, France
  https://www.bell-labs.com, Contact: chung_shue.chen@nokia-bell-labs.com
• Elie de Panafieu, Research Scientist
  Department/Lab: Nokia Bell Labs, Math & Algorithm team, Paris-Saclay, France
  https://www.bell-labs.com, Contact: elie.de_panafieu@nokia-bell-labs.com

Project Description / Internship Subject

A robot moves on a grid or topology. At each position, it perceives the multiset of sensing of the tiles or surroundings that it covers. The goal of the project is to design and code an algorithm that labels the grid so that the robot can uniquely determine its location due to the combination of the sensed labels.

The fewer the number of bits used to represent all the required labels for the system or network, the better.

For example, in the following grid, no two 3-by-3 square contains the same multiset of the labels (we use color to illustrate, which however can mean an identification number or a few bits).

▒ ░ ░ ▒ ░ ░ █

▒ ▒ ░ ░ ▒ █ ░

▒ ░ █ █ █ █ █

░ ▒ ▒ █ █ █ ▒

░ █ ░ ▒ ▒ █ ▒

░ ░ ░ ▒ ▒ █ ▒

░ ▒ ░ ░ ▒ ▒ ▒

(grid)

We would propose interesting new mathematical models which may spur future scientific research. Interesting engineering application includes 6G wireless IoT systems.

Research methodology to be used:

Several approaches of increasing sophistication can be applied. Greedy algorithm, algorithms improving a coloring of graph by solving local conflicts randomly, graph neural networks (as the problem is reminiscent of, but distinct from, graph coloring), machine learning and deep learning techniques. 

References
1. C. Adjih, C. S. Chen, C. S. Gobin, and I. Hmedoush, "Designing Medium Access Control Protocol Sequences Through Deep Reinforcement Learning," European Conference on Networks and Communications & 6G Summit, 2023.
2. Y. Shao, S. C. Liew and T. Wang, "AlphaSeq: Sequence Discovery with Deep Reinforcement Learning," IEEE Trans. on Neural Netw. & Learning Systems, 2020.
3. S.-W. Ho and C. S. Chen, "Visible Light Communication Based Positioning Using Color Sensor," IEEE 8th Optoelectronics Global Conference (OGC), 2023.
4. C. S. Chen, Y.-H. Lo, W. S. Wong, and Y. Zhang, "Object Tracking Using Multiset Color Coding," Preprint, 2024.
5. Etzion, Tuvi. "Sequences and the de Bruijn Graph: Properties, Constructions, and Applications". Academic Press, 2024.

The team:

Inria is the French national research institute for digital science and technology. World-class research, technological innovation and entrepreneurial risk are its DNA. In 220 project teams, most of which are shared with major research universities, often
in an interdisciplinary manner and in collaboration with industrial partners to meet ambitious challenges. Saclay research centre is located at the heart of the Paris-Saclay scientific and technological excellence cluster. Serving the development of the Université Paris-Saclay and the Institut Polytechnique de Paris, the Inria Saclay centre has 60 people working in research support services and 600 scientists working in 37 project teams. It offers a unique environment to talented candidates in the field of technological and software development.

Nokia creates the technologies to connect the world. With the research and innovation capabilities of Nokia Bell Labs, we provide network service providers, governments, large business companies and end users with the most comprehensive portfolio of products, services and licenses on the market. Nokia Bell Labs is the world-renowned research arm of Nokia, having invented many of the foundational technologies that underpin information and communications networks and all digital devices and systems. Within Bell Labs, AI Research Lab conducts fundamental and applied research in machine learning, mathematics, modeling, and optimization. The Lab has a long tradition of excellence in research and currently consists of over 80 staff members with expertise in algorithmic and computing sciences, network measurement and optimization, information theory and machine learning.

Skills that are useful/that you will acquire:

• machine learning and deep learning methods (including Neural Combinatorial Optimization)
• Combinatorics, number and coding method/theory, graph representation and discrete mathematics,
• algorithm design,
• programming and software implementation,
• engineering practice and industrial experience

• Subsidized meals
• Partial reimbursement of public transport costs
• Possibility of teleworking and flexible organization of working hours
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)
• Social, cultural and sports events and activities
• Access to vocational training
• Social security coverage

Gratification