decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  29 {
  30         return this->cusp_;
  31 }
  32
  33 float ParallelSlot::DH() const
  34 {
  35         return this->DH_;
  36 }
  37
  38 PolygonObstacle &ParallelSlot::slot()
  39 {
  40         return this->slot_;
  41 }
  42
  43 float ParallelSlot::slotHeading()
  44 {
  45         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         if (!this->slotSide_) {
  57                 float y0 = this->slot().bnodes()[0]->y();
  58                 float x0 = this->slot().bnodes()[0]->x();
  59                 float y1 = this->slot().bnodes()[1]->y();
  60                 float x1 = this->slot().bnodes()[1]->x();
  61                 float y3 = this->slot().bnodes()[3]->y();
  62                 float x3 = this->slot().bnodes()[3]->x();
  63                 float h1 = atan2(y0 - y3, x0 - x3);
  64                 float h2 = atan2(y1 - y3, x1 - x3);
  65                 if (h2 - h1 > 0)
  66                         this->slotSide_ = LEFT;
  67                 else
  68                         this->slotSide_ = RIGHT;
  69         }
  70         return this->slotSide_;
  71 }
  72
  73 SlotType ParallelSlot::slotType()
  74 {
  75         if (!this->slotType_) {
  76                 float d1 = EDIST(
  77                         this->slot().bnodes()[0],
  78                         this->slot().bnodes()[1]
  79                 );
  80                 float d2 = EDIST(
  81                         this->slot().bnodes()[1],
  82                         this->slot().bnodes()[2]
  83                 );
  84                 if (d1 > d2)
  85                         this->slotType_ = PERPENDICULAR;
  86                 else
  87                         this->slotType_ = PARALLEL;
  88         }
  89         return this->slotType_;
  90 }
  91
  92 // setter
  93 void ParallelSlot::DH(float dh)
  94 {
  95         this->DH_ = dh;
  96 }
  97
  98 // other
  99 void ParallelSlot::fip()
 100 {
 101         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 102         // RRTNode.s() works as iteration level
 103         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 104
 105         // TODO add init nodes
 106         // for now just copy fpose()
 107         bool left = false; // right parking slot
 108         float di = -1;
 109         BicycleCar *CC = new BicycleCar(
 110                 this->fposecenter()->x(),
 111                 this->fposecenter()->y() - 0.01,
 112                 this->slotHeading()
 113         );
 114         BicycleCar *B = new BicycleCar(
 115                 CC->x() - CC->width() / 2,
 116                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 117                 this->slotHeading()
 118         );
 119         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 120                 left = true;
 121                 di = 1;
 122                 delete B;
 123                 B = new BicycleCar(
 124                         CC->x() + CC->width() / 2,
 125                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 126                         this->slotHeading()
 127                 );
 128         }
 129         this->DH(di * 0.01 / CC->out_radi());
 130         BicycleCar *c;
 131         int i = 0;
 132         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 133         while (!this->slot().collide(c->frame())) {
 134                 q.push(c);
 135                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 136                 i += 1;
 137         }
 138         delete c; // not in q and collide
 139         // BFS
 140         while (!q.empty()) {
 141                 c = q.front();
 142                 q.pop();
 143                 if (this->DH() > 0 && c->rfx() <= 0 && c->rrx() <= 0) {
 144                         goto createcuspandfinish;
 145                 } else if (this->DH() < 0 && c->lfx() >= 0 && c->lrx() >= 0) {
 146                         goto createcuspandfinish;
 147                 } else if (c->s() < 9) {
 148                         BicycleCar *cc = this->flnc(c);
 149                         cc->s(c->s() + 1);
 150                         cc->bcparent(c);
 151                         q.push(cc);
 152                 } else {
 153                         delete c; // not in q and collide
 154                 }
 155         }
 156 createcuspandfinish:
 157         std::vector<RRTNode *> cusp;
 158         while (c) {
 159                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 160                 c = c->bcparent();
 161         }
 162         std::reverse(cusp.begin(), cusp.end());
 163         this->cusp().push_back(cusp);
 164         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 165         std::swap(q, empty);
 166 }
 167
 168 void ParallelSlot::fipr(BicycleCar *B)
 169 {
 170         // TODO for right parallel parking also
 171         // it's only for lpar scenario now
 172
 173         std::vector<RRTNode *> cusp;
 174         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 175         // just copied from fip()
 176         this->DH(-0.01 / B->out_radi());
 177         BicycleCar *c;
 178         c = this->flncr(B);
 179         while (c->lfx() < 0) {
 180                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 181                 BicycleCar *cc = this->flncr(c);
 182                 cc->s(c->s() + 1);
 183                 delete c;
 184                 c = cc;
 185         }
 186         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 187         std::reverse(cusp.begin(), cusp.end());
 188         this->cusp().push_back(cusp);
 189 }
 190
 191 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 192 {
 193         // TODO find last not colliding
 194         // for now just copy flast()
 195         RRTNode *cc;
 196         if (int(B->s()) % 2 == 0)
 197                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 198         else
 199                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 200         BicycleCar *p;
 201         int i = 1;
 202         p = B->move(cc, i * this->DH());
 203         while (!this->slot().collide(p->frame())
 204                         && (
 205                                 (this->DH() > 0 && p->x() <= 0)
 206                                 || (this->DH() < 0 && p->x() >= 0)
 207                         )) {
 208                 delete p;
 209                 i += 10;
 210                 p = B->move(cc, i * this->DH());
 211         }
 212         i -= 10;
 213         p = B->move(cc, i * this->DH());
 214         while (!this->slot().collide(p->frame())
 215                         && (
 216                                 (this->DH() > 0 && p->x() <= 0)
 217                                 || (this->DH() < 0 && p->x() >= 0)
 218                         )) {
 219                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 220                         i += 1;
 221                         break;
 222                 }
 223                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 224                         i += 1;
 225                         break;
 226                 }
 227                 delete p;
 228                 i += 1;
 229                 p = B->move(cc, i * this->DH());
 230         }
 231         delete p;
 232         return B->move(cc, (i - 1) * this->DH());
 233 }
 234
 235 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 236 {
 237         // TODO find last not colliding
 238         // for now just copy flast()
 239         RRTNode *cc;
 240         if (int(B->s()) % 2 == 0)
 241                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 242         else
 243                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 244         BicycleCar *p;
 245         int i = 1;
 246         p = B->move(cc, i * this->DH());
 247         while (!this->slot().collide(p->frame())
 248                         && (
 249                                 (this->DH() > 0 && p->x() >= 0)
 250                                 || (this->DH() < 0 && p->lfx() <= 0)
 251                         )) {
 252                 delete p;
 253                 i += 10;
 254                 p = B->move(cc, i * this->DH());
 255         }
 256         i -= 10;
 257         p = B->move(cc, i * this->DH());
 258         while (!this->slot().collide(p->frame())) {
 259                 if (this->DH() > 0 && p->x() <= 0) {
 260                         i += 1;
 261                         break;
 262                 }
 263                 if (this->DH() < 0 && p->lfx() >= 0) {
 264                         i += 1;
 265                         break;
 266                 }
 267                 delete p;
 268                 i += 1;
 269                 p = B->move(cc, i * this->DH());
 270         }
 271         delete p;
 272         return B->move(cc, (i - 1) * this->DH());
 273 }
 274
 275 RRTNode *ParallelSlot::fposecenter()
 276 {
 277         return this->slot().bnodes().front();
 278 }
 279
 280 bool ParallelSlot::flast(
 281         RRTNode *P,
 282         bool right,
 283         int il,
 284         std::vector<RRTNode *> &cusp
 285 )
 286 {
 287         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 288         RRTNode *cc;
 289         if (right)
 290                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 291         else
 292                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 293         BicycleCar *p;
 294         int i = 1;
 295         p = B->move(cc, i * this->DH());
 296         while (!this->slot().collide(p->frame())
 297                         && (
 298                                 (this->DH() > 0 && p->x() <= 0)
 299                                 || (this->DH() < 0 && p->x() >= 0)
 300                         )) {
 301                 delete p;
 302                 i += 10;
 303                 p = B->move(cc, i * this->DH());
 304         }
 305         i -= 10;
 306         p = B->move(cc, i * this->DH());
 307         while (!this->slot().collide(p->frame())
 308                         && (
 309                                 (this->DH() > 0 && p->x() <= 0)
 310                                 || (this->DH() < 0 && p->x() >= 0)
 311                         )) {
 312                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 313                         i += 1;
 314                         break;
 315                 }
 316                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 317                         i += 1;
 318                         break;
 319                 }
 320                 delete p;
 321                 i += 1;
 322                 p = B->move(cc, i * this->DH());
 323         }
 324         delete p;
 325         p = B->move(cc, (i - 1) * this->DH());
 326         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 327                 cusp.push_back(p);
 328                 return true;
 329         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 330                 cusp.push_back(p);
 331                 return true;
 332         } else if (il < 8) {
 333                 cusp.push_back(p);
 334                 return this->flast(p, !right, il + 1, cusp);
 335         }
 336         return false;
 337 }
 338
 339 void ParallelSlot::fpose()
 340 {
 341         bool left = false; // right parking slot
 342         float di = -1;
 343         BicycleCar *CC = new BicycleCar(
 344                 this->fposecenter()->x(),
 345                 this->fposecenter()->y() - 0.01,
 346                 this->slotHeading()
 347         );
 348         BicycleCar *B = new BicycleCar(
 349                 CC->x() - CC->width() / 2,
 350                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 351                 this->slotHeading()
 352         );
 353         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 354                 left = true;
 355                 di = 1;
 356                 delete B;
 357                 B = new BicycleCar(
 358                         CC->x() + CC->width() / 2,
 359                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 360                         this->slotHeading()
 361                 );
 362         }
 363         this->DH(di * 0.01 / CC->out_radi());
 364         BicycleCar *p;
 365         int i = 0;
 366         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 367         while (!this->slot().collide(p->frame())) {
 368                 std::vector<RRTNode *> tmpcusp;
 369                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 370                 if (this->flast(p, left, 0, tmpcusp)) {
 371                         this->cusp().push_back(tmpcusp);
 372                         return;
 373                 }
 374                 i += 1;
 375                 delete p;
 376                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 377         }
 378 }
 379
 380 struct SamplingInfo ParallelSlot::getSamplingInfo()
 381 {
 382         struct SamplingInfo si;
 383         BicycleCar *CC = new BicycleCar(
 384                 this->fposecenter()->x(),
 385                 this->fposecenter()->y() - 0.01,
 386                 this->slotHeading()
 387         );
 388         si.x = this->slot().bnodes()[0]->x();
 389         si.y = this->slot().bnodes()[0]->y();
 390         si.r = CC->diag_radi();
 391         si.h = this->slotHeading() - acos(EDIST( // TODO generalize
 392                 this->slot().bnodes()[0],
 393                 this->slot().bnodes()[1]
 394         ) / BCAR_LENGTH);
 395         return si;
 396 }