ड्रोन और सेल्फ़-ड्राइविंग की बुनियादी बातेंमध्यमपाठ 2847 मिनट का पाठ

रास्ता (path) प्लान करना

दुनिया को खाली और बंद खानों (squares) के एक ग्रिड में बदलें, फिर सबसे छोटा रास्ता खोजें। क्लासिक पाथ प्लानर सीखें: breadth-first search और A*।

✦ ट्यूटर से पूछें 🧪 लैब · 30 min 📝 पाठ का टेस्ट

स्पीड

पाठ वीडियो में

60 सेकंड में

रास्ता (path) प्लान करना

1/4

आसान शब्दों में

सोचिए कि चौखाने वाले कागज़ पर एक भूलभुलैया (maze) बनी है। आप अपनी पेंसिल शुरुआत पर रखते हैं और उसके बगल वाले हर खाने को आज़माते हैं, फिर उनके बगल वाले हर खाने को — ठीक वैसे ही जैसे तालाब में लहरें फैलती हैं। पहली लहर जो बाहर निकलने के रास्ते को छूती है, वही आपको सबसे छोटा रास्ता दिखाती है। एक और समझदारी भरा तरीका: उन खानों को पहले आज़माएँ जो बाहर निकलने की दिशा में हैं। यही A* के पीछे का मुख्य विचार है।

एक बार जब किसी मशीन को पता चल जाता है कि वह कहाँ है, तो उसे तय करना होता है कि जहाँ वह जाना चाहती है वहाँ कैसे पहुँचे। एक आसान और बहुत आम तरीका है दुनिया को एक grid map के रूप में दिखाना: छोटे-छोटे खाने (squares) जो या तो खाली हैं या बंद (blocked)। गोदाम में सामान ढोने वाला रोबोट, फ्लैट में वैक्यूम क्लीनर, या खेत के ऊपर उड़ने वाला ड्रोन — ये सभी इस तरह के ग्रिड का इस्तेमाल कर सकते हैं।

हर खाली खाना वह जगह है जहाँ रोबोट हो सकता है। दो खाने आपस में जुड़े माने जाते हैं अगर रोबोट सीधे उनके बीच जा सके, जैसे ऊपर, नीचे, बाएँ या दाएँ। अब रास्ता खोजना एक खोज (search) बन जाता है: शुरुआत से मंज़िल (goal) तक जुड़े हुए खाली खानों की एक कड़ी ढूँढना।

Breadth-first search (BFS)

BFS शुरुआत से एक बार में एक घेरे की तरह फैलता है: पहले वे सभी खाने जो 1 कदम दूर हैं, फिर जो 2 कदम दूर हैं, और इसी तरह आगे। क्योंकि यह दूरी के क्रम में खोज करता है, इसलिए जैसे ही यह पहली बार मंज़िल तक पहुँचता है, इसे सबसे छोटा रास्ता मिल चुका होता है। BFS आसान और सटीक है, लेकिन यह हर दिशा में खोज करके मेहनत बर्बाद करता है, यहाँ तक कि मंज़िल की उल्टी दिशा में भी।

Python: BFS counts the fewest stepspython

from collections import deque

grid = [
    "S..#....",
    ".#.#.##.",
    ".#...#..",
    ".####.#.",
    "......#G",
]
rows, cols = len(grid), len(grid[0])
start, goal = (0, 0), (4, 7)

dist = {start: 0}
queue = deque([start])
while queue:
    r, c = queue.popleft()
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
            dist[(nr, nc)] = dist[(r, c)] + 1
            queue.append((nr, nc))

print("fewest steps from S to G:", dist.get(goal, "no path"))
print("squares explored:", len(dist))

A*: दिशा की समझ के साथ खोज

A* (इसे "A स्टार" कहें) कंपास के साथ चलने वाले BFS जैसा है। यह हर खाने के लिए दो संख्याएँ रखता है: g, शुरुआत से अब तक चले गए कदम, और h, मंज़िल तक पहुँचने के लिए अभी कितने कदम और चाहिए इसका एक अंदाज़ा। यह हमेशा उस खाने को पहले खोजता है जिसके लिए f = g + h सबसे छोटा हो।

ऐसे ग्रिड पर जहाँ आप ऊपर, नीचे, बाएँ या दाएँ चल सकते हैं, एक अच्छा अंदाज़ा Manhattan distance होता है: पंक्तियों (rows) की दूरी जमा स्तंभों (columns) की दूरी। यह कभी भी ज़रूरत से ज़्यादा अंदाज़ा नहीं लगाता (overestimate नहीं करता), क्योंकि दीवारें असली रास्ते को केवल लंबा ही कर सकती हैं। जब अंदाज़ा कभी ज़रूरत से ज़्यादा नहीं होता, तो A* पक्के तौर पर सबसे छोटा रास्ता ही खोजता है, और यह आमतौर पर BFS के मुकाबले बहुत कम खाने खोजता है।

1
Start
शुरुआती खाने को f = h(start) के साथ प्राथमिकता सूची (priority list) में डालें।
2
Pick
सबसे छोटे f वाले खाने को बाहर निकालें।
3
Goal?
अगर यह मंज़िल है, तो रास्ता पाने के लिए सेव की गई "came from" कड़ियों के सहारे पीछे लौटें।
4
Expand
हर खाली पड़ोसी खाने के लिए, अगर उस तक पहुँचने का यह रास्ता पहले मिले किसी भी रास्ते से छोटा है, तो उसकी लागत और वह कहाँ से आया था यह सेव करें, और उसे f = g + h के साथ जोड़ें।
5
Repeat
जब तक मंज़िल न मिल जाए, या सूची खाली न हो जाए (कोई रास्ता मौजूद नहीं है)।

प्लानर	क्या सबसे छोटा रास्ता खोजता है?	क्या खोजता है	नोट्स
BFS	हाँ, जब हर कदम की लागत बराबर हो	सब कुछ, एक-एक घेरा करके	सबसे आसान और सही तरीका
Dijkstra's algorithm	हाँ, तब भी जब कदमों की लागत अलग-अलग हो	शुरुआत से लागत के क्रम में	अलग-अलग लंबाई या गति वाली सड़कों के लिए
A*	हाँ, अगर अंदाज़ा कभी ज़रूरत से ज़्यादा न हो	ज़्यादातर मंज़िल की दिशा में	नक्शों पर सबसे आम पसंद
Greedy "मंज़िल की तरफ बढ़ो"	नहीं	बहुत कम	तेज़ है लेकिन दीवारों के पीछे अटक सकता है

नोट

असली प्लानर सिर्फ सबसे छोटी रेखा ढूँढने से कहीं ज़्यादा काम करते हैं। वे आसान मोड़ों को प्राथमिकता देते हैं, रुकावटों के पास वाले खानों से बचते हैं, गति सीमा और बैटरी का ध्यान रखते हैं, और कुछ बदलने पर दोबारा प्लान बनाते हैं। कई रोबोट दो परतों (layers) में भी प्लान करते हैं: नक्शे पर एक बड़ा रास्ता (global route), और पास में हिलने-डुलने वाली चीज़ों पर तुरंत प्रतिक्रिया देने वाला एक स्थानीय प्लानर (local planner)।

असली उदाहरण

चेन्नई की एक छोटी टीम एक रोबोट बनाती है जो एक ही मंज़िल पर बने दफ़्तरों के बीच फ़ाइलें ले जाता है। वे फ़्लोर प्लान को एक ग्रिड के रूप में बनाते हैं, दीवारों और अलमारियों को बंद (blocked) मार्क करते हैं, और A* का इस्तेमाल करते हैं। पहले ही दिन यह एक ऐसे दरवाज़े से सीधा रास्ता बना लेता है जो आमतौर पर बंद रहता है। वे एक नया नियम जोड़ते हैं: बंद दरवाज़ों को तब तक बंद माना जाए जब तक सेंसर उन्हें खुला न देख ले। एल्गोरिदम सही था; नक्शा गलत था।

इसे आज़माएँ। BFS कोड में, सबसे ऊपर वाली पंक्ति के # को बदलकर . कर दें। क्या कदमों की गिनती बदलती है? क्या खोजे गए खानों की संख्या बदलती है?

और देखें और पढ़ें

लैब

एक काम करने वाला A* प्लानर जो ग्रिड पर एक मान्य और सबसे छोटा रास्ता खोजे, या बताए कि कोई रास्ता नहीं है।

~30 min

समस्या

यह आपके ब्राउज़र में चलता है। शुरुआती कोड में ग्रिड, पड़ोसी, मैनहट्टन का अंदाज़ा और A* का ज़्यादातर हिस्सा पहले से मौजूद है।

TODO 1 पूरा करें: जब मंज़िल मिल जाए, तो रास्ता बनाने के लिए came_from के ज़रिए पीछे की ओर चलें, और इसे पलट (reverse कर) दें ताकि यह शुरुआत से मंज़िल की ओर हो जाए।
TODO 2 पूरा करें: जब आपको किसी पड़ोसी तक पहुँचने का सस्ता रास्ता मिले, तो उसकी लागत और वह कहाँ से आया यह सेव करें, और उसे हीप (heap) पर पुश करें।
इसे चलाएं। रास्ता * से दिखाया गया है।
एक ऐसी दीवार जोड़ें जो ग्रिड को दो हिस्सों में बाँट दे, और जाँचें कि astar से None मिलता है या नहीं।

यह जाँच आपके प्लानर को कई ग्रिड पर टेस्ट करती है: रास्ता सही जगह से शुरू और खत्म होना चाहिए, एक बार में एक खाना चलना चाहिए, कभी दीवार में नहीं जाना चाहिए, और जितना हो सके उतना छोटा होना चाहिए।

प्रैक्टिस लैब

कोड में बदलाव करें और इसे रन करें। Python आपके ब्राउज़र में चलता है — हमारे सर्वर पर कुछ नहीं भेजा जाता।

रन करने के लिए Ctrl + Enter दबाएं

import heapq

GRID = [
    "S...#.....",
    ".##.#.###.",
    ".#..#...#.",
    ".#.###.#..",
    "...#...#.#",
    ".#...#...G",
]

def find(grid, ch):
    for r, row in enumerate(grid):
        if ch in row:
            return (r, row.index(ch))

def neighbours(grid, cell):
    r, c = cell
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] != "#":
            yield (nr, nc)

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def astar(grid, start, goal):
    """Return the shortest path as a list of (row, col) cells from start to goal,
    including both ends. Return None if there is no path."""
    heap = [(manhattan(start, goal), 0, start)]
    came_from = {start: None}
    cost = {start: 0}
    while heap:
        f, g, cell = heapq.heappop(heap)
        if cell == goal:
            # TODO 1: walk back from goal through came_from, then reverse
            return None
        for nxt in neighbours(grid, cell):
            new_cost = g + 1
            # TODO 2: if nxt is not in cost, or new_cost < cost[nxt]:
            #   save cost[nxt] and came_from[nxt], then push
            #   (new_cost + manhattan(nxt, goal), new_cost, nxt) on the heap
            pass
    return None

start, goal = find(GRID, "S"), find(GRID, "G")
path = astar(GRID, start, goal)
if path is None:
    print("No path found")
else:
    print("Path length (steps):", len(path) - 1)
    rows = [list(row) for row in GRID]
    for r, c in path[1:-1]:
        rows[r][c] = "*"
    print("\n".join("".join(row) for row in rows))

आउटपुट

कोई आउटपुट नहीं। वैल्यूज़ देखने के लिए print(...) जोड़ें।

आपका काम तब पूरा होगा जब

रास्ता S से शुरू होता है, G पर खत्म होता है, एक बार में एक खाना चलता है और कभी दीवार में नहीं जाता
रास्ते की लंबाई सबसे छोटे संभव रास्ते से मेल खाती है (जाँच इसकी तुलना BFS से करती है)
जब कोई दीवार ग्रिड को बाँट देती है, तो astar से None मिलता है
सीखने वाला यह समझा सकता है कि came_from क्या स्टोर करता है और रास्ते को उलटने की ज़रूरत क्यों होती है

कठिन सवाल

उत्तर देखने से पहले ख़ुद जवाब देने की कोशिश करें। अगर आप इनके जवाब दे सकते हैं, तो आप पाठ समझ गए हैं।

Q1अगर आप h = 3 × Manhattan distance का इस्तेमाल करते हैं, तो A* का क्या होगा?दिखाएं

अंदाज़ा अब ज़रूरत से ज़्यादा हो सकता है, इसलिए A* सबसे छोटा रास्ता खोजने की गारंटी नहीं देता। यह ज़्यादा लालची (greedy) बन जाता है: यह मंज़िल की तरफ तेज़ी से भागता है और आमतौर पर कम खाने खोजता है, लेकिन यह कोई लंबा रास्ता भी दे सकता है। कुछ असली सिस्टम तेज़ी से रास्ता प्लान करने के लिए जानबूझकर इसे स्वीकार करते हैं, इस समझौते को weighted A* कहा जाता है।

Q2हीप (heap) f के साथ-साथ g को भी क्यों स्टोर करता है?दिखाएं

ताकि जब किसी खाने को बाहर निकाला जाए, तो हमें उस रास्ते की लागत पता हो जिसने उसे वहाँ पहुँचाया था, और हम उसके पड़ोसियों तक की लागत की गणना कर सकें। एक खाने को अलग-अलग लागतों के साथ एक से ज़्यादा बार पुश किया जा सकता है; हर एंट्री के साथ g को स्टोर करने से हर रास्ते की लागत सही बनी रहती है। कुछ वर्ज़न किसी एंट्री को छोड़ भी देते हैं अगर उस खाने के लिए पहले से ही कोई सस्ता रास्ता पता हो।

जारी रखने के लिए कृपया साइन इन करें।

अक्सर पूछे जाने वाले सवाल

A* को ऐसे अंदाज़े की ज़रूरत क्यों होती है जो कभी ज़रूरत से ज़्यादा न हो?

अगर अंदाज़ा बहुत बड़ा हो सकता है, तो A* को लग सकता है कि कोई अच्छा रास्ता असल से ज़्यादा खराब है, और वह किसी लंबे रास्ते पर खत्म हो सकता है। एक ऐसा अंदाज़ा जो कभी भी ज़रूरत से बड़ा नहीं होता (जिसे admissible कहा जाता है), सबसे छोटे रास्ते को सुरक्षित रखता है। हर जगह शून्य का अंदाज़ा लगाना भी admissible है; तब A* बिल्कुल Dijkstra's algorithm की तरह काम करता है।

क्या हो अगर रोबोट तिरछा (diagonally) भी चल सके?

तब हर खाने के अधिकतम आठ पड़ोसी हो सकते हैं, तिरछे कदमों की लागत आमतौर पर 1 के बजाय लगभग 1.41 होती है, और आपको एक अलग अंदाज़े की ज़रूरत होगी, जैसे कि सीधी रेखा की दूरी। कई प्लानर दीवार के कोने से सटकर तिरछा मुड़ने की भी मनाही करते हैं।

क्या सेल्फ़-ड्राइविंग कारें ग्रिड का इस्तेमाल करती हैं?

अक्सर कुछ हिस्सों में। लंबे रास्तों की प्लानिंग आमतौर पर सड़क के नेटवर्क पर की जाती है, ठीक वैसे ही जैसे कोई मैप ऐप करता है। कार के नज़दीक, सिस्टम अक्सर रुकावटों के आसपास सटीक हलचल प्लान करने के लिए ग्रिड या खाली जगह के अन्य नक्शों का इस्तेमाल करते हैं।

क्या हो अगर नक्शा बहुत बड़ा हो?

3D में या बड़े इलाकों में ग्रिड बहुत बड़े हो जाते हैं। तब प्लानर बड़े खानों वाले ग्रिड, मुख्य जगहों के ग्राफ़, या सैंपलिंग तरीकों का इस्तेमाल करते हैं जो रैंडम बिंदुओं को आज़माते हैं और उन्हें आपस में जोड़ते हैं। लागत और अच्छे अंदाज़े के सिद्धांत वहाँ भी लागू होते हैं।

पाठ का टेस्ट

5 सवाल। पास होने और इस पाठ को पूरा करने के लिए 3 सही होने चाहिए (60%)।

टेस्ट देने और अपनी प्रोग्रेस सेव करने के लिए साइन इन करें

रास्ता (path) प्लान करना

रास्ता (path) प्लान करना

Breadth-first search (BFS)

A*: दिशा की समझ के साथ खोज

Start

Pick

Goal?

Expand

Repeat

और देखें और पढ़ें

समस्या

प्रैक्टिस लैब

आपका काम तब पूरा होगा जब

कठिन सवाल

अक्सर पूछे जाने वाले सवाल